Θεωρία Γραφημάτων

Θεωρία Γραφημάτων

Graph theory

Γέφυρες Konigsberg

- Ένας Επιστημονικός Κλάδος των Μαθηματικών

Ετυμολογία

Η ονομασία "Θεωρία Γραφημάτων" σχετίζεται ετυμολογικά με την λέξη "Γράφημα".

Εισαγωγή

Ένα γράφημα αποτελείται από ένα σύνολο κορυφών V και ένα σύνολο ακμών E. Κάθε στοιχείο του Ε αντιστοιχείται μονοσήμαντα σε ένα συγκεκριμένο ζεύγος στοιχείων του συνόλου V. Αυτός ο απλός ορισμός καθιστά τη Θεωρία Γραφημάτων την κατάλληλη γλώσσα για προσέγγιση των (δυαδικών) σχέσεων συνόλων που αναμφίβολα αποτελεί ευρύτατο θέμα.

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

• η συμπάγεια και
• η επιπεδότητα,
• τα προβλήματα απαρίθμησης (πόσα γραφήματα συγκεκριμένου τύπου υπάρχουν΄),
• προβλήματα χρωματισμού (αναγνώριση διμερών γραφημάτων, το θεώρημα των τεσσάρων χρωμάτων), *διαδρομές,
• κυκλώματα και
• μήκος διαδρομών (το πρόβλημα των γεφυρών του Köningsberg).

Υπάρχει ένας σημαντικός αριθμός θεωρητικών θεμάτων σχετικά με τα γραφήματα που αποτελούν αντικείμενο πολύπλοκης υπολογιστικής μελέτης (το πρόβλημα του περιοδεύοντος πλασιέ, αλγόριθμοι ταξινόμισης, το πρόβλημα των ισόμορφων γραφημάτων).

Η θεωρία επεκτείνεται ακόμη στα προσανατολισμένα, τα σταθμισμένα καθώς και τα πολλαπλώς συνεκτικά γραφήματα.

Θεματολογία

• Υπογραφήματα -
• Συνεκτικά γραφήματα δέντρα -
• Δίκτυα -
• οικονομικότερο παράγων δέντρο (The connector problem).
• Γραφήματα Euler και Hamilton
• ικανή και αναγκαία συνθήκη για γράφημα Euler *αλγόριθμος Fleury.
• Γραφήματα Hamilton: ικανές συνθήκες - Αναγκαίες συνθήκες
• Αλγόριθμος Kaufmann.
• Δυνάμεις γραφημάτων -
• Γραφήματα Hamilton και
• συνεκτικότητα.
• Επίπεδα γραφήματα-
• χρωματισμοί
• τύπος Euler-
• Θεώρημα Kuratowski
• Δυικά γραφήματα-
• γραφήματα welch-Powell
• θεώρημα 5 και 4 χρωμάτων
• θεώρημα Brooks.
• Χρωματισμοί πλευρών
• Θεώρημα Vizing.
• Θεώρημα Menger (για κορυφές, για πλευρές).
• Max-flow,
• min cut.
• θεώρημα Hall (ή του γάμου)
• Σταθεροί γάμοι.
• Πίνακες - Δέντρα.
• Πίνακας γειτνίασης και πρόσπτωσης
• Matrix-tree theorem.
• Απαρίθμηση δέντρων με ονομασία.
• Τύπος Cayler -
• κώδικας Prufer.

Εσωτερική Αρθρογραφία

• Τοπολογία
• [[ ]]

Ιστογραφία

• Ομώνυμο άρθρο στην Βικιπαίδεια
• Ομώνυμο άρθρο στην Livepedia
• [ ]
• [ ]

Κίνδυνοι Χρήσης

Αν και θα βρείτε εξακριβωμένες πληροφορίες σε αυτήν την εγκυκλοπαίδεια ωστόσο, παρακαλούμε να λάβετε σοβαρά υπ' όψη ότι η "Sciencepedia" δεν μπορεί να εγγυηθεί, από καμιά άποψη, την εγκυρότητα των πληροφοριών που περιλαμβάνει. "Οι πληροφορίες αυτές μπορεί πρόσφατα να έχουν αλλοιωθεί, βανδαλισθεί ή μεταβληθεί από κάποιο άτομο, η άποψη του οποίου δεν συνάδει με το "επίπεδο γνώσης" του ιδιαίτερου γνωστικού τομέα που σας ενδιαφέρει." Πρέπει να λάβετε υπ' όψη ότι όλα τα άρθρα μπορεί να είναι ακριβή, γενικώς, και για μακρά χρονική περίοδο, αλλά να υποστούν κάποιο βανδαλισμό ή ακατάλληλη επεξεργασία, ελάχιστο χρονικό διάστημα, πριν τα δείτε. Επίσης, Οι διάφοροι "Εξωτερικοί Σύνδεσμοι (Links)" (όχι μόνον, της Sciencepedia αλλά και κάθε διαδικτυακού ιστότοπου (ή αλλιώς site)), αν και άκρως απαραίτητοι, είναι αδύνατον να ελεγχθούν (λόγω της ρευστής φύσης του Web), και επομένως είναι ενδεχόμενο να οδηγήσουν σε παραπλανητικό, κακόβουλο ή άσεμνο περιεχόμενο. Ο αναγνώστης πρέπει να είναι εξαιρετικά προσεκτικός όταν τους χρησιμοποιεί.

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

---

>>Διαμαρτυρία προς την wikia<<

- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)

---