Μίλησε για ένα μη προσανατολισμένο γράφο και τις ιδιότητές του.

Ένα μη προσανατολισμένο γράφημα είναι ένα ζεύγος $(V, E)$, όπου $V$ είναι το σύνολο των κορυφών (κόμβων), και $E$ είναι το σύνολο των ακμών. Κάθε άκρη αντιπροσωπεύει ένα μη διατεταγμένο ζεύγος ${u, v}$ κορυφών, όπου $u, v \in V$.

Βασικές ιδιότητες:

• Άκρες χωρίς κατεύθυνση: Η σύνδεση μεταξύ κορυφών είναι συμμετρική. Αν υπάρχει άκρη μεταξύ $u$ και $v$, αυτό σημαίνει ότι μπορείς να κινηθείς τόσο από $u$ σε $v$ όσο και από $v$ σε $u$.
• Βαθμός κορυφής: Ο αριθμός των ακμών που είναι incident σε αυτήν την κορυφή. Αναπαρίσταται ως $deg(v)$.
• Άθροισμα βαθμών όλων των κορυφών: Σε κάθε μη προσανατολισμένο γράφημα, το άθροισμα των βαθμών όλων των κορυφών είναι ίσο με τον διπλάσιο του αριθμού των ακμών. $\sum_{v \in V} deg(v) = 2|E|$.
• Διαδρομή: Διαδοχή κορυφών $v_0, v_1, ..., v_k$, όπου κάθε ζεύγος $(v_i, v_{i+1})$ είναι μια άκρη.
• Κύκλος: Μια διαδρομή που ξεκινά και τελειώνει στην ίδια κορυφή, και όλες οι άλλες κορυφές είναι μοναδικές.
• Συνδεσιμότητα: Ένα γράφημα ονομάζεται συνεκτικό αν υπάρχει διαδρομή μεταξύ κάθε ζεύγους κορυφών. Ένα μη συνεκτικό γράφημα αποτελείται από πολλαπλές συνδετικές συνιστώσες.
• Ζυγισμένο γράφημα: Σε κάθε άκρη μπορεί να αποδοθεί μια αριθμητική τιμή (βάρος).
• Απουσία βρόχων και πολλαπλών ακμών (απλό γράφημα): Σε απλά μη προσανατολισμένα γραφήματα, μεταξύ δύο κορυφών μπορεί να υπάρχει το πολύ μία άκρη, και οι άκρες δεν συνδέουν μια κορυφή με τον εαυτό της (χωρίς βρόχους).
• Πλήρες γράφημα: Γράφημα στο οποίο κάθε ζεύγος διαφορετικών κορυφών είναι συνδεδεμένο με μια άκρη. Αναπαρίσταται ως $K_n$, όπου $n$ είναι ο αριθμός των κορυφών.
• Διμερές γράφημα: Το σύνολο των κορυφών μπορεί να διαιρεθεί σε δύο διακριτά υποσύνολα $U$ και $W$, έτσι ώστε κάθε άκρη να συνδέει μια κορυφή από το $U$ με μια από το $W$.