Αποστάσεις - Θεωρία Γραφημάτων και Εφαρμογές

Ίχνος-trail είναι ένας περίπατος όπου κάθε κορυφή εμφανίζεται το πολύ μία φορά.

• Σωστό

• Λάθος

Μονοπάτι είναι ένα ίχνος όπου μια κορυφή εμφανίζεται το πολύ μία φορά (δεν τέμνεται με τον εαυτό του και δεν περιέχει βρόχους).

• Σωστό

• Λάθος

Μήκος περιπάτου είναι το πλήθος

• κορυφών που περιλαμβάνονται στον γράφο.

• ακμών που περιλαμβάνονται στον γράφο.

• υπο-γράφων που περιλαμβάνονται στον γράφο.

• μονοπατιών που περιλαμβάνονται στον γράφο.

Κάθε κύκλος είναι κύκλωμα

• και κάθε κύκλωμα είναι κύκλος

• ενώ κάθε κύκλωμα δεν είναι απαραίτητα κύκλος

Δύο μονοπάτια λέγονται ξένα ως προς τις ακμές –

edge disjoint,

• αν έχουν έως το πολύ μία κοινή ακμή.

• αν δεν έχουν κάποια κοινή ακμή .

• αν δεν έχουν κοινές κορυφές.

• αν έχουν έως το πολύ μία κοινή κορυφή.

Γεωδεσικό-geodesic μονοπάτι μεταξύ δύο κορυφών είναι

• το συντομότερο μονοπάτι.

• το μεγαλύτερο μονοπάτι.

Ένας γράφος λέγεται γεωδεσικός αν υπάρχει ένα μοναδικό γεωδεσικό μονοπάτι για δύο οποιεσδήποτε κορυφές του.

• Σωστό

• Λάθος

Εκκεντρικότητα-eccentricity μιας κορυφής v είναι

• η απόσταση από την κορυφή v προς την λιγότερο απομακρυσμένη κορυφή του γράφου.

• η απόσταση από την κορυφή v προς την πλέον απομακρυσμένη κορυφή του γράφου.

• η απόσταση από την κορυφή v προς όλες τις υπόλοιπες κορυφές του γράφου.

• η κορυφή που δεν προσπίπτει σε καμία ακμή, γι' αυτό και χαρακτηρίζεται εκκεντρική (ή κορυφή-diva).