Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete Mathematics > Graphs > Flashcards

Graphs Flashcards

1
Q

Τι είναι γράφος?

A

Ένα σύνολο κορυφών (ή κόμβων) που συνδέονται με
ένα σύνολο ακμών

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Τι είναι ένας μη κατευθυνόμενος γράφος?

A

Ένας γράφος στον οποίο οι ακμές δεν έχουν προσανατολισμό

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Τι είναι ένας κατευθυνόμενος γράφος (directed/oriented)?

A

Είναι ο γράφος που αποτελείται από ένα μη κενό σύνολο κορυφών και διατεταγμένα ζεύγη κορυφών που συνδέονται με τόξα (arcs)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Τι είναι ένας ζυγισμένος γράφος (weighted graph)?

A

Για κάθε ακμή ενός γράφου, w(e) είναι το βάρος (weight) αυτής και αν υπάρχει, τότε έχουμε ζυγισμένο γράφο

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Μπορείς να αναπαραστήσεις έναν γράφο με διαφορετικούς τρόπους?

A

Ναι, αρκεί οι κορυφές και οι ακμές να ενώνονται με τον ίδιο τρόπο. Στην περίπτωση ενός ζυγισμένου γράφου, τα βάροι των ακμών πρέπει να είναι αντίστοιχα.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Τι είναι ένα ελάχιστο ζευγνύοντο δέντρο (MST)?

A

Ένα Ελάχιστο Ζευγνύοντο Δέντρο (Minimum Spanning Tree - MST) είναι ένα υπογράφημα ενός συνδεδεμένου γράφου που περιέχει όλους τους κόμβους του αρχικού γράφου και ορισμένες ακμές, ώστε να συνδέει όλους τους κόμβους με τον ελάχιστο δυνατό τρόπο, δηλαδή με το ελάχιστο δυνατό συνολικό κόστος (ή βάρος) για τις επιλεγμένες ακμές.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Τι ονομάζεται τάξη (οrder)?

A

Το πλήθος των κορυφών: n=|V|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Τι ονομάζεται μέγεθος (size)?

A

Το πλήθος των ακμών: m=|Ε|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Πότε ονομάζουμαι έναν γράφο, αραιό (sparse)?

A

Όταν η τάξη του είναι συγκρίσιμη με το μέγεθος του, n ≈ m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Πότε ονομάζουμαι ένα γράφο, πυκνό (sparse)?

A

Όταν το τετράγωνο της τάξη του είναι συγκρίσιμο με το μέγεθος του, n^2 ≈ m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Πότε ονομάζουμαι ένα γράφο, πεπερασμένο (finite)?

A

Όταν η τάξη και το μέγεθός του (n,m) είναι πεπερασμένα

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Πότε ονομάζουμαι ένα γράφο, άπειρο (infinite)?

A

Όταν η τάξη και το μέγεθός του (n,m) είναι άπειρα

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Πως ονομάζεται ο γράφος στις περιπτώσεις
- n=0
- n=1
- m=0

A

n=0 := κενός (empty)
n=1 := ασήμαντος (trivial)
m=0 := μηδενικός (null)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Τι ονομάζουμαι, τερματικά σημεία ακμής (endpoints)?

A

Τις κορυφές μιας ακμής

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Τι ονομάζουμαι, ακμές προσπίπτουσες σε κορυφή (incident)?

A

Τις ακμές που ενώνονται με μια συγκεκριμένη κορυφή

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Τι ονομάζουμαι, γειτονικές κορυφές (neighbor)?

A

Κορυφές οι οποίες έχουν κοινή ακμή

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Τι ονομάζουμαι, ανεξάρτητες κορυφές (independent)?

A

Κορυφές οι οποίες δεν έχουν κοινές ακμές

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Τι ονομάζουμαι, γειτονιά κορυφής (neighborhood)?

A

Ένα σύνολο κορυφών σε ένα γράφο που είναι άμεσα συνδεδεμένες με μια δεδομένη κορυφή
π.χ. Ν(Β) = {A, C}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Τι ονομάζουμαι, παράλληλες ακμές (parallel)?

A

Τις ακμές που ενώνουν το ίδιο ζεύγος κορυφών

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Τι ονομάζουμαι, βρόγχο (self-loop)?

A

Μια ακμή η οποία ενώνεται δύο φορές με την ίδια κορυφή

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Τι ονομάζουμαι, βαθμό κορυφής (degree)?

A

Το πλήθος των ακμών που συνδεέται με την κορυφή
π.χ. d(A) = 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Τι ονομάζουμαι, ελάχιστο και μέγιστο βαθμό ενός γράφου?

A

Τον ελάχιστος και μέγιστο αριθμός ακμών που είναι συνδεδεμένες με έναν κόμβο ανάλογα
π.χ. d(G)=2, D(G)=5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Τι ονομάζεται, απομονωμένη κορυφή (isolated)?

A

Μια κορυφή που δεν είναι ενωμένη με ακμές

24
Q

Τι ονομάζεται, εκκρεμής κορυφή (pendant)?

A

Μια κορυφή που είναι ενωμένη με μόνο μια ακμή

25
Q

Τι ονομάζουμαι, συνδεδεμένες συνιστώσες (connected components)?

A

Αν V1,…,Vk είναι ανεξάρτητα υποσύνολα κορυφών, τότε οι υπογράφοι G(V1),…,G(Vk) είναι οι συνδεδεμένες συνιστώσες (connected components) του γράφου G

26
Q

Τι ονομάζουμαι, συνδεδεμένο γράφο (connected)?

A

Τον γράφο που αποτελείται από μία μόνο συνιστώσα

27
Q

Τι σημαίνει, ο γράφος είναι συνδεδεμένος κατά ελάχιστο τρόπο (minimally connected)?

A

Αν η διαγραφή μιας μόνο ακμής του γράφου, τον αποσυνδέει και δημιουργεί συνιστώσες

28
Q

Τι ονομάζουμαι, σειρά (rank) ενός γράφου?

A

r = n – k, όπου n η τάξη και k το πλήθος των συνιστωσών

29
Q

Τι ονομάζουμαι, μηδενικότητα (nullity) ενός γράφου?

A

Το ελάχιστο πλήθος από ακμές που πρέπει να αφαιρεθούν από το γράφο για να αφαιρεθούν όλοι οι κύκλοι του και να μετατραπεί σε δέντρο/δάσος: μ = m – n + k

30
Q

Τι ονομάζουμαι, απλό γράφο (simple)?

A

Τον γράφο που δεν περιλαμβάνει παράλληλες ακμές ή βρόχους

31
Q

Τι ονομάζουμαι, ψευδογράφο (pseudograph)?

A

Τον γράφο που περιλαμβάνει βρόγχους

32
Q

Τι ονομάζουμαι, πουλυγράφο (multigraph)?

A

Έναν γράφο με παράλληλες ακμές αλλά χωρίς βρόχους

33
Q

Τι ονομάζουμαι, υποκείμενο γράφο (underlying)?

A

Τον γράφο που προκύπτει αν απαλειφθούν οι βρόχοι και οι παράλληλες ακμές

34
Q

Τι είναι ο περίπατος (walk)?

A

Mία ακολουθία W=(v1, e1, v2, e2,…,ei-1, vi) από κορυφές και ακμές, που αρχίζει και τελειώνει με κορυφή, έτσι ώστε η ακμή ej να προσπίπτει στις κορυφές vj και vj+1, για 1 ≤ j < i

35
Q

Τι είναι ίχνος (trail)?

A

Ένας περίπατος όπου κάθε ακμή εμφανίζεται το πολύ μία φορά

36
Q

Τι είναι μονοπάτι (path)?

A

ένα ίχνος όπου μια κορυφή εμφανίζεται το πολύ μία φορά (δεν τέμνεται με τον εαυτό του και δεν περιέχει βρόχους)

37
Q

Ποιο είναι το μήκος περιπάτου/ ίχνους/ μονοπατιού?

A

Το πλήθος ακμών που περιλαμβάνονται
n: Pn

38
Q

Σημαντικές κορυφές περιπάτου/ ίχνους/ μονοπατιού

A
  • Αρχή (origin), τέρμα (terminus)
  • Τερματικές (terminal) (αρχή+τέρμα) vs. εσωτερικές (internal) κορυφές
39
Q

Τι σημαίνει αν αρχή=τέρμα

A

Αν είναι ίχνος, τότε είναι κλειστό ίχνος (κύκλωμα)
Αν είναι μονοπάτι, τότε είναι κλειστό μονοπάτι (κύκλος)

40
Q

Τι σημαίνει αν αρχή!=τέρμα

A

Αν είναι ίχνος, τότε ανοικτό ίχνος
Αν είναι μονοπάτι, τότε ανοκτό μονοπάτι

41
Q

Πότε ονομάζεται ένας κύκλος άρτιος και πότε περιττός?

A

Ένας κύκλος μήκους k λέγεται άρτιος ή περιττός αν το k είναι άρτιο ή περιττό, αντιστοίχως

42
Q

Σχέση κύκλου - κυκλώματος?

A

Κάθε κύκλος είναι κύκλωμα, ενώ κάθε κύκλωμα δεν είναι απαραίτητα κύκλος

43
Q

Τι ονομάζουμαι δένδρα και δάσοι?

A

Τα δένδρα είναι άκυκλοι συνδεδεμένοι γράφοι, ενώ δάσος είναι ένας γράφος με δένδρα ως συνιστώσες

44
Q

Πότε λέγονται δύο μονοπάτια λέγονται ξένα ως προς τις ακμές (edge disjoint)?

A

Όταν δεν έχουν κάποια κοινή ακμή (παρότι μπορεί να τέμνονται)

45
Q

Πότε δύο κορυφές ονομάζονται συνδεδεμένες (connected)?

A

Όταν υπάρχει κάποιο μονοπάτι από τη μια κορυφή προς την άλλη

46
Q

Είναι κάθε κορυφή συνδεδεμένη με τον εαυτό της?

A

Ναι

47
Q

Τι ονομάζουμαι γεωδεσικό μονοπάτι (geodesic) μεταξύ δύο κορυφών?

A

Το συντομότερο μονοπάτι

48
Q

Τι ονομάζουμαι απόσταση dist(u,v) μεταξύ των κορυφών u,v?

A

Το μήκος του γεωδεσικού μονοπατιού των κορυφών u,v.

49
Q

Ποίες είναι οι ιδιότητες της απόστασης?

A
  • Μη αρνητικότητα: dist(u,v) > 0, αν u=v => dist(u,v) = 0
  • Συμμετρική: dist(u,v) = dist(v,u)
50
Q

Τι λέει η ανιστότητα τριγώνου?

A

dist(u,v) + dist(v,z) >= dist(u,z)

51
Q

Πότε ονομάζεται ένας γράφος γεωδεσικός? Σχέση με τα δένδρα?

A

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

52
Q

Τι ονομάζουμαι “Ένωση γράφων”?

A

Ένωση (union) δύο γράφων είναι ο γράφος G= G1⋃ G2 με σύνολο κορυφών V(G) = V1 ⋃ V2 και σύνολο ακμών E(G) = E1⋃ E2

53
Q

Ποιές είναι οι ιδιότητες της ένωσης γράφων?

A
  • Κάθε μη συνδεδεμένος γράφος μπορεί να εκφρασθεί ως ένωση δύο ή περισσοτέρων συνιστωσών
  • Η ένωση m ισομορφικών γράφων G συμβολίζεται με mG
  • Αν ένας γράφος G μπορεί να εκφρασθεί ως ένωση των παραγόντων του (factor) (ή ζευγνυόντων υπογράφων), τότε η ένωση αυτή ονομάζεται παραγοντοποίηση του G
  • Ένας παράγοντας που είναι τακτικός γράφος βαθμού r καλείται rπαράγοντας. Αν ένας γράφος αποτελείται μόνο από r-παράγοντες τότε λέγεται r-παραγοντοποιήσιμος
54
Q

Τι ονομάζουμαι “Τομή γράφων”?

A

Τομή (intersection) δύο γράφων G = G1⋂ G2 είναι ο γράφος G με σύνολο κορυφών V(G) = V1 ⋂ V2 και σύνολο ακμών E(G) = E1⋂ E2

55
Q

Τι ονομάζουμαι “Τομή δακτυλίου”?

A

Άθροισμα δακτυλίου (ring sum), G = G1⊕ G2 είναι ο γράφος G με σύνολο κορυφών V(G) = V1⋃ V2 και σύνολο ακμών E(G) = (E1⋃ E2) – (E1⋂ E2)

56
Q
A

Discrete Mathematics (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions