Γράφος
ένα σύνολο κορυφών και ένα σύνολο ακμών που συνδέουν ζεύγη των κορυφών / From Wikipedia, the free encyclopedia
Στα διακριτά μαθηματικά, ένας γράφος ή ένα γράφημα είναι μια αφηρημένη αναπαράσταση ενός συνόλου στοιχείων, όπου μερικά ζεύγη στοιχείων συνδέονται μεταξύ τους με δεσμούς. Τα διασυνδεδεμένα στοιχεία αναπαριστώνται με μαθηματικές έννοιες οι οποίες ονομάζονται κορυφές ή κόμβοι ενώ οι δεσμοί που συνδέουν τα ζευγάρια των κορυφών ονομάζονται ακμές. Συνήθως, ένα γράφημα απεικονίζεται σε διαγραμματική μορφή ως ένα σύνολο κουκκίδων για τις κορυφές, ενωμένα μεταξύ τους με γραμμές ή καμπύλες για τις ακμές. Οι γράφοι είναι ένα από τα αντικείμενα μελέτης στα διακριτά μαθηματικά.
Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν. |
Οι ακμές μπορούν να είναι κατευθυνόμενες (ασύμμετρες) ή μη-κατευθυνόμενες (συμμετρικές). Για παράδειγμα, εάν οι κορυφές αντιπροσωπεύουν τα άτομα σε ένα πάρτι, και υπάρχει ακμή μεταξύ δύο ανθρώπων, αν δίνουν τα χέρια, τότε αυτό είναι ένα μη-κατευθυνόμενο γράφημα, γιατί αν το πρόσωπο Α έδωσε τα χέρια με το πρόσωπο Β, τότε και το πρόσωπο Β έδωσε τα χέρια και με πρόσωπο Α. Από την άλλη πλευρά, εάν οι κορυφές αντιπροσωπεύουν τα άτομα σε ένα πάρτι και υπάρχει μια ακμή από το πρόσωπο Α στο πρόσωπο Β όταν το πρόσωπο Α γνωρίζει το πρόσωπο Β, τότε η γραφική αυτή παράσταση είναι κατευθυνόμενη γιατί το να γνωρίζεις κάποιον δεν είναι απαραίτητα μια συμμετρική σχέση (δηλαδή, ένα άτομο που γνωρίζει ένα άλλο πρόσωπο δεν συνεπάγεται κατ 'ανάγκη το αντίθετο, για παράδειγμα, πολλοί άνθρωποι μπορεί να γνωρίζουν μια διάσημη προσωπικότητα αλλά η διάσημη προσωπικότητα είναι απίθανο να γνωρίζει όλους τους οπαδούς της). Το τελευταίο αυτό είδος γραφήματος ονομάζεται κατευθυνόμενο γράφημα και οι ακμές του ονομάζονται κατευθυνόμενες ακμές ή τόξα.
Οι κορυφές καλούνται επίσης κόμβοι ή σημεία, και οι ακμές ονομάζονται επίσης γραμμές. Τα γραφήματα είναι το βασικό θέμα μελέτης από τη θεωρία γραφημάτων. Η λέξη «γράφημα» χρησιμοποιήθηκε για πρώτη φορά με αυτή την έννοια από τον James Joseph Sylvester το 1878.