« nazaj
Diskretne strukture (FiM) - vaje 23.12.2020
Teorija grafov
Naloga 1
Pokaži, da so hiperkocke dvodelni grafi.
Hiperkocka ${Q_n} = (V, E)$:
- $V = \lbrace 0, 1 \rbrace^n = A + B$
- $E = \lbrace \lbrace u, v \rbrace \mid u-v \text{ ima natanko en neničeln element} \rbrace$
- $A = \lbrace u \in V \mid u \text{ ima sodo število enic} \rbrace$
- $B = \lbrace v \in V \mid v \text{ ima liho število enic} \rbrace$
- za vsako povezavo $\lbrace u, v \rbrace \in E$ velja $u \in A$ in $v \in B$
- graf ${Q_n}$ je torej dvodelen
Naloga 2
Poišči graf povezav spodnjega grafa. Izračunaj, koliko vozlišč in koliko povezav ima graf povezav v splošnem.
graph G {
rankdir=LR
a -- b
a -- c
b -- c
b -- d
c -- e
d -- e
}
Za graf $G = (V, E)$ je graf povezav $L(G) = (V’, E’)$ tak graf, da velja:
- $V’ = E$
- $\lbrace e, f \rbrace \in E’ \iff |e \cap f| = 1$
- $|V’| = |E|$
- $|E’| = {1 \over 2} {\sum_{e \in E}} {d_{L(G)}(e)} = {\sum_{u \in V}} {d_G(u) \choose 2}$
- ${d_{L(G)}(\lbrace u, v \rbrace)} = {d_G(u)} + {d_G(v)} - 2$
graph LG {
rankdir=LR
ab -- ac
ab -- bc
ab -- bd
ac -- bc
ac -- ce
bc -- bd
bc -- ce
bd -- de
ce -- de
}
- Stopnje v $G$: 2, 2, 2, 3, 3
- $3 \cdot {2 \choose 2} + 2 \cdot {3 \choose 2} = 3 + 6 = 9$ povezav
Naloga 3
Pokaži, da je kartezični produkt dvodelnih grafov $G$ in $H$ dvodelen graf.
- Dana sta grafa $G = ({V_1}, {E_1})$, $H = ({V_2}, {E_2})$.
- Kartezični produkt $G \square H = (V, E)$:
- $V = {V_1} \times {V_2} = \lbrace ({u_1}, {u_2}) \mid {u_1} \in {V_1}, {u_2} \in {V_2} \rbrace$
- $\lbrace ({u_1}, {u_2}), ({v_1}, {v_2}) \rbrace \in E \iff (\lbrace {u_1}, {v_1} \rbrace \in {E_1} \land {u_2} = {v_2}) \lor ({u_1} = {v_1} \land \lbrace {u_2}, {v_2} \rbrace \in {E_2})$
- Predpostavimo, da sta $G$ in $H$ dvodelna z razdelitvama množic vozlišč ${V_1} = {A_1} + {B_1}$ in ${V_2} = {A_2} + {B_2}$
- $A = {A_1} \times {A_2} + {B_1} \times {B_2}$
- $B = {B_1} \times {A_2} + {A_1} \times {B_2}$
- vse povezave iz $E$ imajo eno krajišče v $A$ in eno krajišče v $B$
- graf $G \square H$ je torej dvodelen
Za hiperkocke velja ${Q_{m+n}} = {Q_n} \square {Q_m}$.
Naloga 4
Izračunaj premer hiperkocke ${Q_n}$.
- Razdalja med vozliščema $u, v$: $\partial(u, v) =$ dolžina najkrajše poti od $u$ do $v$
- Premer grafa $G = (V, E)$: $D(G) = {\max_{u, v \in V}} \partial(u, v)$
Hiperkocka ${Q_n} = (V, E)$:
- $\partial(u, v) = \sum_{i=1}^n |{u_i} - {v_i}|$
- $D({Q_n}) = n$
graph Q2 {
rankdir=LR
00 -- 01
00 -- 10
01 -- 11
10 -- 11
}
Naloga 5
V cirkuški predstavi nastopajo $4$ pari klovnov: $2$ rdeča, $2$ modra, $2$ zelena in $2$ rumena. Med predstavo se zaletavajo med seboj, a nikoli se ne zaletita dva klovna iste barve. Nekega dne je prvi rdeči klovn vprašal ostalih $7$, v koliko drugih klovnov so se zaleteli. Dobil je same različne odgovore. V koliko klovnov se je med predstavo zaletel drugi rdeči klovn? Zapiši nalogo v jeziku teorije grafov in jo reši.
Prirejeno po S. Klavžar, Presek, letnik 26, številka 2, strani 72-78.
$G = (V, E)$:
- $V$ … klovni
- $\lbrace u, v \rbrace \in E$ … $u$ in $v$ sta se zaletela
- stopnje: 0, 1, 2, 3, 4, 5, 6, $x \in \lbrace 1, 3, 5 \rbrace$
graph klovni {
node[style=filled]
R1[color=red]
R2[color=red]
M1[color=blue]
M2[color=blue]
Z1[color=green]
Z2[color=green]
Y1[color=yellow]
Y2[color=yellow]
M1 -- R1
M1 -- R2
M1 -- Z1
M1 -- Z2
M1 -- Y1
M1 -- Y2
Z1 -- R1
Z1 -- R2
Z1 -- Y1
Z1 -- Y2
Y1 -- R1
Y1 -- R2
}
Oba rdeča klovna sta se zaletela trikrat.
Naloga 6
Naj bo $G = (V, E)$ enostaven graf z minimalno stopnjo vsaj $\lfloor n/2 \rfloor$, kjer je $n = |V|$. Pokaži, da je potem $G$ povezan.
Graf $G = (V, E)$ je povezan, če za vsaki vozlišči $u, v \in V$ obstaja pot od $u$ do $v$ v grafu $G$.
- Naj bosta $u, v \in V$ nesosednji vozlišči.
- Naj bosta $A$ in $B$ množici sosedov vozlišč $u$ oziroma $v$.
- Vemo $|A|, |B| \ge \lfloor n/2 \rfloor$.
- $|\lbrace u, v \rbrace \cup A \cup B|$ $\stackrel{?}{=}$ $|\lbrace u, v \rbrace| + |A| + |B| \ge 2 + n - 1 = n + 1$
- enačaja ne moremo imeti, torej množici $A, B$ nista disjunktni
- torej obstaja $w \in A \cap B$ in tako obstaja pot $uwv$
- graf $G$ je torej povezan
Naloga 7
Naj bo $G = (V, E)$ enostaven graf. Pokaži, da je tedaj $G$ povezan ali pa je povezan njegov komplement.
Denimo, da graf $G = (V, E)$ ni povezan. Naj bosta $u, v \in V$.
- Če $\lbrace u, v \rbrace \not\in E$, potem $\lbrace u, v \rbrace \in \overline{E}$.
- Če $\lbrace u, v \rbrace \in E$, naj bo $w$ vozlišče v drugi povezani komponenti kot $u, v$. Potem v $\overline{G}$ obstaja pot $uwv$.
Graf $\overline{G}$ je torej povezan.
Naloga 8
Naj bo $G = (V, E)$ povezan graf. Povezava $e \in E$ je most, če $G \backslash \lbrace e \rbrace$ ni več povezan. Pokaži: če ima $G$ most, potem ima vsaj dve vozlišči lihe stopnje.