Μικτά Γραφήματα Moore και Σχεδόν–Γραφήματα Moore

Τα Μικτά Γραφήματα Moore αποτελούν ένα ιδιαίτερο κεφάλαιο στη θεωρία γραφημάτων, συνδυάζοντας κατευθυνόμενες και μη κατευθυνόμενες ακμές σε ένα ενιαίο μαθηματικό αντικείμενο. Ο στόχος τους είναι η κατασκευή γραφημάτων με μέγιστο δυνατό αριθμό κορυφών για δεδομένο βαθμό και διάμετρο.

Η μελέτη τους συνδέεται στενά με το λεγόμενο όριο Moore, το οποίο δίνει το θεωρητικό ανώτατο όριο για το πλήθος κορυφών ενός γράφου συγκεκριμένων παραμέτρων. Ένα γράφημα που επιτυγχάνει ακριβώς αυτό το όριο ονομάζεται γράφημα Moore. Αν πλησιάζει το όριο χωρίς να το φτάνει, χαρακτηρίζεται ως σχεδόν–Moore γράφημα.

---

🔹 Ορισμός και Ιδιότητες

Σε ένα μικτό γράφημα $G$, για κάθε κορυφή $u$:

• $r(u)$ είναι ο μη κατευθυνόμενος βαθμός (ο αριθμός των ακμών που προσπίπτουν στο $u$),

• $z^+(u)$ είναι ο βαθμός εξόδου (ο αριθμός των ακμών που ξεκινούν από το $u$),

• $z^-(u)$ είναι ο βαθμός εισόδου (ο αριθμός των ακμών που καταλήγουν στο $u$).

Αν ισχύει ότι
$z^+(u) = z^-(u) = z$ και $r(u) = r$ για κάθε $u \in V$,
τότε το γράφημα $G$ ονομάζεται εντελώς κανονικό βαθμών $(r, z)$ ή απλά (r, z)-κανονικό.

Η παράμετρος $d = r + z$ αντιπροσωπεύει τον συνολικό βαθμό κάθε κορυφής.

---

🔹 Παραδείγματα και Σχήματα

Η έρευνα των C. Dalfó, M. A. Fiol και N. López παρουσιάζει μια σειρά από μικτά γραφήματα που ικανοποιούν ή πλησιάζουν τα όρια Moore.

Σχήμα 1. Το μικτό γράφημα Bosák, ένα γράφημα Moore με μη κατευθυνόμενο βαθμό 3, κατευθυνόμενο βαθμό 1, διάμετρο 2 και 18 κορυφές.

Σχήμα 2. (α) Το μοναδικό γνωστό σχεδόν–Moore γράφημα με διάμετρο 2. (β) Ένα γράφημα τάξης 10 και διαμέτρου 2 που ικανοποιεί την Εξίσωση (2) χωρίς να είναι εντελώς κανονικό.

Σχήμα 3. Τα μοναδικά τρία μη ισόμορφα σχεδόν–Moore μικτά γραφήματα με διάμετρο $k = 3$ και κατευθυνόμενο βαθμό $z = 1$.

Σχήμα 4. Δύο μη ισόμορφα μικτά γραφήματα με παράλληλα τόξα, κοσμοφασματικά με τα $H(i)$, για $i = 1, 2, 3$.

---

🔹 Ο Τύπος Moore

Ένα φυσικό άνω όριο για τον αριθμό κορυφών ενός μικτού γραφήματος $N(r, z, k)$, γνωστό ως όριο τύπου Moore, προκύπτει μετρώντας τις κορυφές ενός δέντρου Moore $MT(u)$, ρίζας $u$ και βάθους ίσου με τη διάμετρο $k$.

Η ακριβής τιμή αυτού του αριθμού δίνεται από τη σχέση:

$$M(r, z, k) = A \frac{u_1^{k+1} - 1}{u_1 - 1} + B \frac{u_2^{k+1} - 1}{u_2 - 1},$$

όπου

$$v = (z+r)^2 + 2(z−r) + 1, \quad u_1 = \frac{z+r−1−\sqrt{v}}{2}, \quad u_2 = \frac{z+r−1+\sqrt{v}}{2},$$

και

$$A = \frac{\sqrt{v}−z+r−1}{2\sqrt{v}}, \quad B = \frac{\sqrt{v}+z+r+1}{2\sqrt{v}}.$$

Η μορφή αυτών των εκφράσεων θυμίζει λύσεις αναδρομικών σχέσεων τύπου Fibonacci, γεγονός που δεν είναι τυχαίο — καθώς το μοτίβο προκύπτει από την καταμέτρηση των περιπάτων σε ένα δέντρο Moore.

---

🔹 Συμπεράσματα

Τα μικτά γραφήματα Moore και σχεδόν–Moore γραφήματα αποτελούν θεμελιώδες εργαλείο στη μελέτη των ορίων πυκνότητας και συμμετρίας στη θεωρία γραφημάτων.

Αν και τα πλήρη γραφήματα Moore είναι εξαιρετικά σπάνια, τα σχεδόν–Moore γραφήματα αποκαλύπτουν πλούσιες δομές με ιδιαίτερη κανονικότητα και συμμετρία, ενώ συνεχίζουν να εμπνέουν τη σύγχρονη έρευνα στη μαθηματική θεωρία δικτύων.