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.