Κατευθυνόμενος γράφος: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ r2.7.2) (Ρομπότ: Προσθήκη: et:Suunatud graaf |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 49:
===Βασική ορολογία===
Ένα τόξο <math>e = (x, y)</math> κατευθύνεται '''από''' το <math>x</math> '''προς το''' <math>y</math>. Το <math>y</math> ονομάζεται '''κεφαλή''' και το <math>x</math> ονομάζεται '''ουρά''' του βέλους. Το <math>y</math> είναι ο '''άμεσος απόγονος''' του <math>x</math>, και το <math>x</math> είναι ο '''άμεσος πρόγονος''' του <math>y</math>. Έαν υπάρχει ένα [[Γράφος#Μονοπάτια και είδη|μονοπάτι]] από ένα ή περισσότερα διαδοχικά τόξα που συνδέει το <math>x</math> με το <math>y</math>, τότε λέμε ότι το <math>y</math> είναι '''απόγονος''' του <math>x</math>, και ότι το <math>x</math> είναι '''πρόγονος''' του <math>y</math>. Το τόξο <math
Ένας κατευθυνόμενος γράφος ''G'' ονομάζεται '''συμμετρικός''' αν, για κάθε τόξο που ανήκει στο ''G'', το αντίστοιχο ανεστραμμένο τόξο ανήκει επίσης στο ''G''. Ένας συμμετρικός κατευθυνόμενος γράφος που δεν περιέχει βρόχους είναι ισοδύναμος με έναν μη κατευθυνόμενο γράφο όπου κάθε ζευγάρι από ανεστραμμένα τόξα έχει αντικατασταθεί από μία ακμή. Έτσι ο αριθμός των ακμών του μη κατευθυνόμενου γράφου είναι ίσος με το μισό του αριθμού των τόξων του κατευθυνόμενου γράφου.
Γραμμή 69:
Ο τύπος του αθροίσματος των βαθμών, για έναν κατευθυνόμενο γράφο είναι,
:<math
Εάν για κάθε κορυφή <math>v </math>, <math>\deg^+(v) = \deg^-(v)</math>, τότε ο γράφος ονομάζεται '''ισορροπημένος κατευθυνόμενος γράφος'''.
| |||