TeorijaGrafov Flashcards
Kaj je graf?
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
Kaj je stopnja vozlišča grafa?
a. Stopnja vozlišča je število povezav, ki imajo V za krajišče. Označimo deg(v)
kaj pravi lema o rokovanju?
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
Kdaj pravimo, da je zaporedje naravnih števil grafično?
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, ..
Kdaj sta u in v sosednji točki?
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.
Kaj je stopnja točke?
Stopnja točke v ∈ V(G) je število povezav, ki imajo v za krajišče. Stopnjo točke v označimo z
deg(v).
Kaj je list
Točki stopnje 1 pa pravimo tudi
list grafa.
kaj je izolirna točka?
Točka stopnje 0 je izolirna točka (torej nima sosednjih točk).
Kdaj je graf regularen oz. d-regularen?
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.
Kaj je grafično zaporedje?
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
Kdaj pravimo da sta grafa izomorfna?
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
Kdaj je graf poln?
Graf je poln, če sta vsaki njegovi točki sosedi. Poln graf na n točkah označimo z Kn
Kdaj je graf prazen?
Graf je prazen, če nobeni njegovi točki nista sosedi. Prazen graf na n točkah označimo z Kongruentno Kn
Kaj je polni dvodelni graf?
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.
Kako je definiran podgraf?
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)
Kaj je vpet podgraf?
Podgraf grafa G je vpet podgraf, če je V(H) = V(G)
Kaj je sprehod v grafu?
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
Kaj pravi lema o sprehodu v grafu?
Č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.
Kdaj je graf povezan?
Graf G je povezan, če za vsaki dve vozlišči u, v ∈ V(G) v grafu G obstaja u – v sprehod.
Kdaj je graf dvodelen?
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.
Kdaj je sprehod v grafu enostaven?
Sprehod v grafu G je enostaven, če vsako povezavo uporabi največ enkrat
Kdaj je graf G dvodelen?
a. Če graf ne vsebuje ciklov lihe stopnje ali
b. Če je kromatično število natanko 2 – lahko pobarvamo z 2 barvama
Kaj so povezane komponente grafa G?
a. Povezane komponente (drevesa) predstavljajo gozd.
b. Gozd – graf, ki ne vsebuje nobenega cikla
c. Če je gozd povezan, ga imenujemo drevo.
Kaj je Eulerjev obhod?
Eulerjev obhod je enostaven sprehod v grafu G, ki vsebuje vse povezave in vse točke grafa.
Kdaj je graf Eulerjev?
Graf G je Eulerjev, če ima kak Eulerjev obhod.
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.
Kaj je Hamiltonov cikel?
Hamiltonov cikel je takšen cikel v grafu G, ki vsebuje vse točke grafa G
Kdaj je graf Hamiltonov?
Graf G je Hamiltonov, če vsebuje kak Hamiltonov cikel
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.
Kaj je drevo?
Drevo je povezan graf brez ciklov
Kaj je gozd?
Gozd je graf brez ciklov
Kakšna je povezava med drevesi in gozdovi (trditev)?
G je gozd <=> povezane komponente G so drevesa.
G je drevo <=> G je povezan gozd
Kaj je prerezna točka?
v ∈ V(G) je prerezna točka grafa G, če ima G – v strogo več povezanih komponent kot G.
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
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
Kdaj je graf povezan?
Graf G je povezan natanko tedaj, ko ima vsaj eno vpeto drevo.
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.
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
Kaj je kromatično število χ(G) grafa G?
Kromatično število predstavlja najmanjše število barv, s katerim lahko
pobarvamo graf
