1.4 Βαθμός κορυφών

Ο βαθμός μιας κορυφής u ενός γραφήματος G συμβολίζεται με d_G(u) και είναι ίσος με τον αριθμό των ακμών που έχουν ως άκρο τους την κορυφή u. (Κάθε βρόχος υπολογίζεται για δύο ακμές ).

Θεώρημα 1.1: Απόδειξη:
Κάθε ακμή έχει δύο άκρα. Επομένως κάθε ακμή "συνεισφέρει" τον αριθμό 2 στο άθροισμα Άρα Το Θεώρημα 1.1 θεωρείται σαν το πρώτο της Θεωρίας Γραφημάτων.
Με δ(G) και Δ(G) συμβολίζουμε τον ελάχιστο και μέγιστο βαθμό κορυφών αντίστοιχα σ' ένα γράφημα G.

1.5 Μονοπάτια , κύκλοι και συνεκτικότητα

Μια πεπερασμένη ακολουθία W = υ_oe₁υ₁e₂ υ₂ . . . e_k υ_k, της οποίας οι όροι είναι αλληλοδιαδόχως κορυφές και ακμές, όπου για 1 < i < k τα άκρα της ακμής e_i, είναι οι κορυφές υ_i-1 και υ_i, ονομάζεται περίπατος στο G. Οι κορυφές υ_ο και υ_k ονομάζονται αρχή και τέλος αντίστοιχα του περιπάτου W.
Οι κορυφές υ₁ , υ₂ , . . . , υ_k ονομάζονται εσωτερικές κορυφές του W. Στα απλά γραφήματα ο περίπατος υ_oe₁υ₁e₂ υ₂ . . . e_k υ_k μπορεί να προσδιορισθεί με την ακολουθία των κορυφών του, δηλαδή με την υ_oυ₁ υ₂ . . . υ_k .
Εάν οι ακμές e₁ , e₂ , . . . , e_k του περιπάτου W είναι διαφορετικές μεταξύ τους, τότε ο W ονομάζεται ίχνος. Εάν ο W είναι κλειστός περίπατος όπου δεν παρατηρείται επανάληψη εσωτερικών κορυφών, τότε ο W ονομάζεται κύκλος. Εάν τώρα οι κορυφές υ_o , υ₁ , υ₂ , . . . , υ_k του W είναι διαφορετικές μεταξύ τους, τότε ο W ονομάζεται μονοπάτι.
Ένα γράφημα ονομάζεται συνεκτικό, αν για κάθε ζεύγος διαφορετικών κορυφών του, u και υ, υπάρχει μονοπάτι με αρχή την u και τέλος την υ. Ένα τέτοιο μονοπάτι ονομάζεται (u , υ) - μονοπάτι.
Συνιστώσα ενός γραφήματος G ονομάζουμε ένα συνεκτικό υπογράφημά του H, το οποίο δεν περιέχεται σε άλλο συνεκτικό υπογράφημα του G που έχει περισσότερες κορυφές ή ακμές από το H. Ο αριθμός των συνιστωσών του G συμβολίζεται με ω(G) και ω(G)=1. εάν και μόνον εάν το G είναι συνεκτικό.

Προηγούμενο

Ευρετήριο

Επόμενο