Κατευθυνόμενοι και μη κατευθυνόμενοι γράφοι

[Marfoto2]

Καλησπέρα.
Σύμφωνα  με το βιβλίο:
Εάν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνό-
μενος γράφος (directed graph).
Εάν όλες οι ακμές σε έναν γράφο δεν έχουν κατεύθυνση, ο γράφος ονομάζεται μη
κατευθυνόμενος γράφος (undirected graph).

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

[pgrontas]

.

[evry]

Νομίζω ήρθε η ώρα να ορίσουμε τον ημι-κατευθυνόμενο γράφο.

[gpapargi]

Πέρυσι αν θυμάμαι καλά το είχαμε ξανασυζητήσει και ήξερα κι εγώ ότι οι γράφοι είναι είτε κατευθυνόμενοι είτε μη κατευθυνόμενο. Τώρα βρήκα αυτό για μικτούς γράφους
https://en.wikipedia.org/wiki/Mixed_graph

[pgrontas]

Πέρυσι αν θυμάμαι καλά το είχαμε ξανασυζητήσει και ήξερα κι εγώ ότι οι γράφοι είναι είτε κατευθυνόμενοι είτε μη κατευθυνόμενο. Τώρα βρήκα αυτό για μικτούς γράφουςhttps://en.wikipedia.org/wiki/Mixed_graphp

Όντως. Και από ό,τι φαίνεται δεν είναι γενικά ισοδύναμα. Οπότε τελικά το βιβλίο είναι σωστό και εγώ έκανα το λάθος.

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

Και αν το σκεφτείς βγάζει νόημα: αν μεταξύ δύο σημείων υπάρχει δρόμος διπλής κατεύθυνσης και γίνει μία πορεία μάλλον θα κλείσουν και τα δύο ρεύματα. Ενώ αν υπάρχουν δύο ξεχωριστοί παράλληλοι δρόμοι μονής αλλά αντίθετης κατεύθυνσης κάτι τέτοιο είναι λιγότερο πιθανό.