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

Ξεκίνησε από lala, 29 Φεβ 2024, 02:44:45 ΜΜ

« προηγούμενο - επόμενο »

lala

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

pgrontas

#1
Ο γράφος που περιγράφεις είναι ισοδύναμος με έναν γράφο με μία κατευθυνόμενη ακμή μονής κατεύθυνσης  (α-->β) και τις υπόλοιπες σπασμένες σε διπλής κατεύθυνσης (α --> β και β-->α). Άρα είναι κατευθυνόμενος.
Το ερώτημα πάντως είναι πολύ κακό γιατί κανένας δεν θα δούλευε με έναν 'μικτό γράφο'. Δεν ξέρω τι θέλει να εξετάσει.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

lala

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

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

pgrontas

Παράθεση από: lala στις 01 Μαρ 2024, 10:50:32 ΠΜΕάν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνόμενος γράφος (directed graph).
Εάν όλες οι ακμές σε έναν γράφο δεν έχουν κατεύθυνση, ο γράφος ονομάζεται μη κατευθυνόμενος γράφος (undirected gr.

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

Διαπιστώνετε και εσείς ότι η ερώτηση είναι κακή.
Σε κάθε περίπτωση αν και το βιβλίο ως ορισμό έχει αυτό που παραθέσατε, στο παράδειγμα με τα κοινωνικά δίκτυα (Facebook) αναφέρει ότι μια μη κατευθυνόμενη ακμή είναι αμφίδρομη (δηλ. - δική μου επεξήγηση - ισοδύναμη με δύο κατευθυνόμενες ακμές αντιθετης φοράς)
Οπότε έτσι δικαιολογείται ότι αν στην κακή αυτή ερώτηση έπρεπε υποχρεωτικά να δοθεί απάντηση (πχ. αν είχε πέσει στις πανελλήνιες) η μόνη αποδεκτή απαντήση θα ηταν ότι πρόκειται για κατευθυνόμενο γράφο, με την αιτιολογία που σας έδωσα παραπάνω.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

Παράθεση από: lala στις 01 Μαρ 2024, 10:50:32 ΠΜΠαραθέτω τον ορισμό απο το σχολικό βιβλίο...για να είναι κατευθυνόμενος θα πρέπει να έχει όλες τις ακμές με κατευθυνση. 

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

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

akalest0s

Όντως δεν πρέπει να ζητηθεί κάτι τέτοιο (έχει ξανασυζητηθεί).
Η προσπάθεια για κάποιο έξυπνο ή πονηρό ερώτημα, πρέπει να στοχεύσει σε άλλα σημεία, και όχι στον τύπο γράφου. 
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK