TeorijaGrafov

Question 1

Kaj je graf?

Answer 1

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

Question 2

Kaj je stopnja vozlišča grafa?

Answer 2

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

Question 3

kaj pravi lema o rokovanju?

Answer 3

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

Question 4

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

Answer 4

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, ..

Question 5

Kdaj sta u in v sosednji točki?

Answer 5

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.

Question 6

Kaj je stopnja točke?

Answer 6

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

Question 7

Kaj je list

Answer 7

Točki stopnje 1 pa pravimo tudi

list grafa.

Question 8

kaj je izolirna točka?

Answer 8

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

Question 9

Kdaj je graf regularen oz. d-regularen?

Answer 9

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.

Question 10

Kaj je grafično zaporedje?

Answer 10

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

Question 11

Kdaj pravimo da sta grafa izomorfna?

Answer 11

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

Question 12

Kdaj je graf poln?

Answer 12

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

Question 13

Kdaj je graf prazen?

Answer 13

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

Question 14

Kaj je polni dvodelni graf?

Answer 14

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.

Question 15

Kako je definiran podgraf?

Answer 15

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)

Question 16

Kaj je vpet podgraf?

Answer 16

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

Question 17

Kaj je sprehod v grafu?

Answer 17

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

Question 18

Kaj pravi lema o sprehodu v grafu?

Answer 18

Č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.

Question 19

Kdaj je graf povezan?

Answer 19

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

Question 20

Kdaj je graf dvodelen?

Answer 20

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.

Question 21

Kdaj je sprehod v grafu enostaven?

Answer 21

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

Question 22

Kdaj je graf G dvodelen?

Answer 22

a. Če graf ne vsebuje ciklov lihe stopnje ali

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

Question 23

Kaj so povezane komponente grafa G?

Answer 23

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

Question 24

Kaj je Eulerjev obhod?

Answer 24

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

Question 25

Kdaj je graf Eulerjev?

Answer 25

Graf G je Eulerjev, če ima kak Eulerjev obhod.

Question 26

Kaj pravi Eulerjev izrek?

Answer 26

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.

Question 27

Kaj je Hamiltonov cikel?

Answer 27

Hamiltonov cikel je takšen cikel v grafu G, ki vsebuje vse točke grafa G

Question 28

Kdaj je graf Hamiltonov?

Answer 28

Graf G je Hamiltonov, če vsebuje kak Hamiltonov cikel

Question 29

Kaj je potrebni pogoj za Hamiltonov graf (izrek) ?

Answer 29

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.

Question 30

Kaj je drevo?

Answer 30

Drevo je povezan graf brez ciklov

Question 31

Kaj je gozd?

Answer 31

Gozd je graf brez ciklov

Question 32

Kakšna je povezava med drevesi in gozdovi (trditev)?

Answer 32

G je gozd <=> povezane komponente G so drevesa.

G je drevo <=> G je povezan gozd

Question 33

Kaj je prerezna točka?

Answer 33

v ∈ V(G) je prerezna točka grafa G, če ima G – v strogo več povezanih komponent kot G.

Question 34

Kaj je prerezna povezava?

Answer 34

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

Question 35

Kaj je vpeto drevo?

Answer 35

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

Question 36

Kdaj je graf povezan?

Answer 36

Graf G je povezan natanko tedaj, ko ima vsaj eno vpeto drevo.

Question 37

Kaj lahko poveš o barvanju grafa?

Answer 37

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.

Question 38

Kdaj je graf Hamiltonov? Navedite Diracov zadostni pogoj za obstoj
Hamiltonovega cikla v grafu.

Answer 38

Naj bo G graf z vsaj tremi točkami (|V (G)|) = n ≥ 3 če za vsako točko v velja:
deg(v) > n/2

Question 39

Kaj je kromatično število χ(G) grafa G?

Answer 39

Kromatično število predstavlja najmanjše število barv, s katerim lahko
pobarvamo graf