TeorijaGrafov Flashcards

1
Q

Kaj je graf?

A

a. Graf je urejen par G = (V , E) , kjer je:
i. V neprazna končna množica točk grafa G in
ii. E množica povezav grafa G , pri čemer je vsaka povezava par točk

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

Kaj je stopnja vozlišča grafa?

A

a. Stopnja vozlišča je število povezav, ki imajo V za krajišče. Označimo deg(v)

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

kaj pravi lema o rokovanju?

A

b. Lema o rokovanju - vsota vseh stopenj vozlišč je enaka 2*m
Posledica: V vsakem grafu je sodo mnogo točk lihe stopnje.
Posledica: Naj bo G d-regularen graf z n točkami in m povezavami. Potem je n * d = 2 * m

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

Kdaj pravimo, da je zaporedje naravnih števil grafično?

A

Zaporedje D1 ≥ D2 ≥ D3 ≥ Dn je grafično, če obstaja graf z točkami, ki 1 2 3 . . . ≥ n, ki imajo stopnje enake D1, D2, ..

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

Kdaj sta u in v sosednji točki?

A

Točki u in v sta sosedi, kadar sta krajišči iste povezave e (povezava e povezuje točki u in v).
To označimo z u ~ v.

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

Kaj je stopnja točke?

A

Stopnja točke v ∈ V(G) je število povezav, ki imajo v za krajišče. Stopnjo točke v označimo z
deg(v).

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

Kaj je list

A

Točki stopnje 1 pa pravimo tudi

list grafa.

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

kaj je izolirna točka?

A

Točka stopnje 0 je izolirna točka (torej nima sosednjih točk).

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

Kdaj je graf regularen oz. d-regularen?

A

Graf G je regularen če imajo vse njegove točke isto stopnjo.

Graf G je d-regularen, če imajo vse njegove točke stopnjo d.

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

Kaj je grafično zaporedje?

A

Končno zaporedje naravnih števil d1 >= d2 >= d3 … dn je grafično, če obstaja graf G z n točkami,
ki imajo stopnjo enake d1, d2, d3 … dn
Posledica: zaporedje d1 >= d2 >= d3 … dn je grafično natanko tedaj, ko požrešna metoda uspe

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

Kdaj pravimo da sta grafa izomorfna?

A

Grafa G in H sta izomorfna, če obstaja preslikava f: V(G) –> V(H), za katero velja:
a) F je bijektivna
b) U ~ g v <=> f(u) ~ h f(v)
Trditev: izomorfizem ohranja število vozlišč, število povezav, stopnjo vozlišč, število
trikotnikov …
V nasprotnem primeru pravimo da sta grafa neizomorfna

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

Kdaj je graf poln?

A

Graf je poln, če sta vsaki njegovi točki sosedi. Poln graf na n točkah označimo z Kn

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

Kdaj je graf prazen?

A

Graf je prazen, če nobeni njegovi točki nista sosedi. Prazen graf na n točkah označimo z Kongruentno Kn

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

Kaj je polni dvodelni graf?

A

Km, n je polni dvodelni graf na n+m točkah. Vsebuje dva barvna razreda s po n in m točkami,
točki sta sosedi natanko tedaj, ko sta v različnih barvnih razredih.

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

Kako je definiran podgraf?

A
Naj bosta H in G grafa. Pravimo, da je H podgraf grafa G (pišemo H ⊆ G), če je V(H) ⊆ V(G)
in E(H) ⊆ E(G)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Kaj je vpet podgraf?

A

Podgraf grafa G je vpet podgraf, če je V(H) = V(G)

17
Q

Kaj je sprehod v grafu?

A

Sprehod S v grafu G=(V, E) je zaporedje vozlišč u0, u1, u2 … un pri čemer sta zaporedni vozlišči
sprehoda ui in ui+1 sosedi v grafu G

18
Q

Kaj pravi lema o sprehodu v grafu?

A

Če v grafu G = (V, E) obstaja u – v sprehod S potem v G obstaja tudi u – v pot.
Posledica: najkrajši u – v sprehod v grafu je pot.

19
Q

Kdaj je graf povezan?

A

Graf G je povezan, če za vsaki dve vozlišči u, v ∈ V(G) v grafu G obstaja u – v sprehod.

20
Q

Kdaj je graf dvodelen?

A

Graf G je dvodelen, če lahko točke grafa G pobarvamo z dvema barvama tako, da ima vsaka
povezava krajišči različnih barv.
Izrek: Graf G je dvodelen natanko tedaj, ko G ne vsebuje ciklov lihe dolžine.

21
Q

Kdaj je sprehod v grafu enostaven?

A

Sprehod v grafu G je enostaven, če vsako povezavo uporabi največ enkrat

22
Q

Kdaj je graf G dvodelen?

A

a. Če graf ne vsebuje ciklov lihe stopnje ali

b. Če je kromatično število natanko 2 – lahko pobarvamo z 2 barvama

23
Q

Kaj so povezane komponente grafa G?

A

a. Povezane komponente (drevesa) predstavljajo gozd.
b. Gozd – graf, ki ne vsebuje nobenega cikla
c. Če je gozd povezan, ga imenujemo drevo.

24
Q

Kaj je Eulerjev obhod?

A

Eulerjev obhod je enostaven sprehod v grafu G, ki vsebuje vse povezave in vse točke grafa.

25
Kdaj je graf Eulerjev?
Graf G je Eulerjev, če ima kak Eulerjev obhod.
26
Kaj pravi Eulerjev izrek?
Graf G je Eulerjev natanko tedaj, ko je G povezan in so vse njegove točke sodih stopenj. Posledica: Graf G je Eulerjev natanko tedaj, ko ga lahko narišemo z eno samo potezo, ki je povrh vsega še sklenjena.
27
Kaj je Hamiltonov cikel?
Hamiltonov cikel je takšen cikel v grafu G, ki vsebuje vse točke grafa G
28
Kdaj je graf Hamiltonov?
Graf G je Hamiltonov, če vsebuje kak Hamiltonov cikel
29
Kaj je potrebni pogoj za Hamiltonov graf (izrek) ?
Naj bo G povezan graf. Denimo da obstaja takšna podmnožica točk v ⊆ V(G) moči |S| = k, za katero velja, da ima G-S vsaj k+1 povezanih komponent. Potem G ni Hamiltonov. Komentar: Pogoj, da v grafu takšna množica S ne obstaja, je potreben. To pomeni, da vsak Hamiltonov graf zadošča temu pogoju. Toda če graf pogoju zadošča, to še ne pomeni da je Hamiltonov.
30
Kaj je drevo?
Drevo je povezan graf brez ciklov
31
Kaj je gozd?
Gozd je graf brez ciklov
32
Kakšna je povezava med drevesi in gozdovi (trditev)?
G je gozd <=> povezane komponente G so drevesa. | G je drevo <=> G je povezan gozd
33
Kaj je prerezna točka?
v ∈ V(G) je prerezna točka grafa G, če ima G – v strogo več povezanih komponent kot G.
34
Kaj je prerezna povezava?
e ∈ E(G) je prerezna povezava grafa G, če ima G – e strogo več povezanih komponent kot G. Trditev: e ∈ E(G) je prerezna povezava natanko tedaj, ko e ne leži na nobenem ciklu g grafa G
35
Kaj je vpeto drevo?
Naj bo G graf in H ⊆ G. H je vpeto drevo v G, če je: a) H je vpet podgraf v G b) H je drevo
36
Kdaj je graf povezan?
Graf G je povezan natanko tedaj, ko ima vsaj eno vpeto drevo.
37
Kaj lahko poveš o barvanju grafa?
k-barvanje točk grafa G je preslikava c: V(G) --> {1, 2, 3 ... k } za katero velja, da je c(u) ≠c(v). To pomeni, da morata biti krajišči vsake povezave različnih barv. Najmanjše naravno število k, za katerega obstaja k-barvanje točk grafa G, imenujemo kromatično število grafa G. Z w(G) označimo velikost največjega polnega podgrafa v G. Velja w(G) ≤ 2 natanko tedaj, ko je G brez trikotnikov. Δ(G) označuje največjo stopnjo točke v grafu G z π(G) pa označimo najmanjšo stopnjo točke grafa G.
38
Kdaj je graf Hamiltonov? Navedite Diracov zadostni pogoj za obstoj Hamiltonovega cikla v grafu.
Naj bo G graf z vsaj tremi točkami (|V (G)|) = n ≥ 3 če za vsako točko v velja: deg(v) > n/2
39
Kaj je kromatično število χ(G) grafa G?
Kromatično število predstavlja najmanjše število barv, s katerim lahko pobarvamo graf