Γραφος: Κατευθυνόμενος ή μη κατευθυνόμενος

[lala]

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

[pgrontas]

Ο γράφος που περιγράφεις είναι ισοδύναμος με έναν γράφο με μία κατευθυνόμενη ακμή μονής κατεύθυνσης  (α-->β) και τις υπόλοιπες σπασμένες σε διπλής κατεύθυνσης (α --> β και β-->α). Άρα είναι κατευθυνόμενος.
Το ερώτημα πάντως είναι πολύ κακό γιατί κανένας δεν θα δούλευε με έναν 'μικτό γράφο'. Δεν ξέρω τι θέλει να εξετάσει.

[lala]

Εάν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνόμενος γράφος (directed graph).
Εάν όλες οι ακμές σε έναν γράφο δεν έχουν κατεύθυνση, ο γράφος ονομάζεται μη κατευθυνόμενος γράφος (undirected gr.

Παραθέτω τον ορισμό απο το σχολικό βιβλίο...για να είναι κατευθυνόμενος θα πρέπει να έχει όλες τις ακμές με κατευθυνση. Απο τον ορισμό του σχολικού εγω καταλαβαίνω οτι οταν εχω διπλή κατεύθυνση εχω μη κατευθυνόμεπο γραφο. Οπότε πως προκύπτει ο κατευθυνόμενος γράφος?
ευχαριστώ

[pgrontas]

Εάν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνόμενος γράφος (directed graph).
Εάν όλες οι ακμές σε έναν γράφο δεν έχουν κατεύθυνση, ο γράφος ονομάζεται μη κατευθυνόμενος γράφος (undirected gr.

Παραθέτω τον ορισμό απο το σχολικό βιβλίο...για να είναι κατευθυνόμενος θα πρέπει να έχει όλες τις ακμές με κατευθυνση. Απο τον ορισμό του σχολικού εγω καταλαβαίνω οτι οταν εχω διπλή κατεύθυνση εχω μη κατευθυνόμεπο γραφο. Οπότε πως προκύπτει ο κατευθυνόμενος γράφος?
ευχαριστώ

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

[gpapargi]

Παραθέτω τον ορισμό απο το σχολικό βιβλίο...για να είναι κατευθυνόμενος θα πρέπει να έχει όλες τις ακμές με κατευθυνση. 

Πάλι όμως από τον ορισμό του βιβλίου, για να είναι μη κατευθυνόμενος θα πρέπει να έχει όλες τις ακμές χωρίς κατεύθυνση. 
Άρα με βάση τον ορισμό δεν είναι τίποτα από τα δύο. ΑΠό ότι είδα στους ορισμούς εκτός σχολικού, αν το σύνολο των ακμών έχει για στοιχεία διατεταγμένα ζεύγη (α,β) είναι κατευθυνόμενος γιατί στα ζεύγη μετράει η σειρά. Αν έχει σύνολα {α,β} είναι μη κατευθυνόμενος γιατί δε μετράει η σειρά. 
Είδα βιβλιογραφικά ότι υπαρχουν μεικτοί γράφοι με κάποιες ακμές κατευθυνόμενες και κάποιες μη κατευθυνόμενες.
https://en.wikipedia.org/wiki/Mixed_graph

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

[akalest0s]

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