owned this note
owned this note
Published
Linked with GitHub
---
tags: vaje, ds, grafi
hackmd: https://hackmd.io/k5KtmtjhQF-yyZ2ddCc5zQ
plugins: mathjax, viz.js
---
# Diskretne strukture (FiM) - vaje 6.1.2021
---
## Teorija grafov
Drevesa: povezani grafi brez ciklov
* $T = (V, E)$
* <i>$|E| = |V| - 1$</i>
Poln dvodelen graf ${K_{m,n}} = (V, E)$
* $V = A + B$, <i>$|A| = m$</i>, <i>$|B| = n$</i>
* $E = \lbrace \lbrace u, v \rbrace \mid u \in A, v \in B \rbrace$
Primer ${K_{2,3}}$
```graphviz
graph K23 {
a -- 1
a -- 2
a -- 3
b -- 1
b -- 2
b -- 3
}
```
* Eulerjev obhod: obhod po vozliščih grafa (začnemo in končamo v istem vozlišču), kjer obiščemo vse povezave (posamezno vozlišče lahko obiščemo večkrat).
- Graf ima Eulerjev obhod natanko tedaj, ko imajo vsa vozlišča sodo stopnjo.
* Eulerjev sprehod: sprehod po vozliščih grafa (začnemo in končamo lahko v različnih vozliščih), kjer obiščemo vse povezave (posamezno vozlišče lahko obiščemo večkrat).
- Graf ima Eulerjev sprehod natanko tedaj, ko imamo največ dve vozlišči lihe stopnje.
* Hamiltonov cikel: obhod po vozliščih grafa, kjer vsako vozlišče obiščemo natanko enkrat.
* Hamiltonova pot: sprehod po vozliščih grafa, kjer vsako vozlišče obiščemo natanko enkrat.
- Iskanje Hamiltonovih ciklov in poti je v splošnem težek problem!
---
### Naloga 1
Dokaži, da so vsa drevesa dvodelni grafi. Kateri polni dvodelni grafi so drevesa?
----
* Drevo nima ciklov, torej tudi lihih ciklov nima, torej je dvodelen graf.
* ${K_{1, n}} \cong {K_{n, 1}}$ zvezda
* ${K_{m, n}}$, $m, n \ge 2$: $u, v \in A$, $x, y \in B$, cikel $uxvy$, torej ni drevo
```graphviz
graph K14 {
a -- 1
a -- 2
a -- 3
a -- 4
}
```
---
### Naloga 2
Naj bo $T$ drevo in $v$ njegovo vozlišče (koren drevesa). Naj ima vsako vozlišče stopnjo $3$ ali $1$, razen korena $v$, ki ima stopnjo $2$. Takemu drevesu pravimo **dvojiško drevo**. Naj bodo vsi listi na razdalji $d$ od korena $v$. Koliko listov ima $T$?
----
* Število listov: $2^d$
* Število vozlišč: ${\sum_{i=0}^d} 2^i = 2^{d+1} - 1$
```graphviz
graph T {
v -- a
v -- b
a -- c
a -- d
b -- e
b -- f
}
```
---
### Naloga 3
Naj bo $T$ drevo s $17$ vozlišči, ki so vsa stopnje $1$ ali $4$. Koliko vozlišč stopnje $4$ ima $T$? Nariši kakšno takšno drevo.
----
* <i>$|E| = |V| - 1 = 16$</i>
* $x$ ... št. vozlišč stopnje 4
* Lema o rokovanju: <i>$\sum_{u \in V(T)} {d_T}(u) = x \cdot 4 + (17-x) \cdot 1 = 2|E| = 32$</i>
* $3x = 15$
* $x = 5$
```graphviz
graph T {
a -- b
a -- c
a -- d
a -- e
b -- f
b -- g
b -- h
c -- i
c -- j
c -- k
d -- l
d -- m
d -- n
e -- o
e -- p
e -- q
}
```
---
### Naloga 4
Poišči vsa neizomorfna drevesa na $10$ vozliščih brez vozlišč stopnje $2$. Nato si oglej povezavi:
* <https://www.youtube.com/watch?v=N7b0cLn-wHU>
* <https://www.youtube.com/watch?v=iW_LkYiuTKE>
----
$T = (V, E)$
* <i>$|V| = 10$</i>
* <i>$|E| = 9$</i>
* $\forall u \in V: {d_T}(u) \ne 2$
$1^9, 9$:
```graphviz
graph T1 {
a -- b
a -- c
a -- d
a -- e
a -- f
a -- g
a -- h
a -- i
a -- j
}
```
$1^8, 3, 7$:
```graphviz
graph T2 {
a -- b
b -- c
b -- d
a -- e
a -- f
a -- g
a -- h
a -- i
a -- j
}
```
$1^8, 4, 6$:
```graphviz
graph T3 {
a -- b
b -- c
b -- d
b -- e
a -- f
a -- g
a -- h
a -- i
a -- j
}
```
$1^8, 5^2$:
```graphviz
graph T4 {
a -- b
b -- c
b -- d
b -- e
b -- f
a -- g
a -- h
a -- i
a -- j
}
```
$1^7, 3^2, 5$:
```graphviz
graph T5 {
a -- b
b -- c
b -- d
g -- e
g -- f
a -- g
a -- h
a -- i
a -- j
}
```
```graphviz
graph T6 {
a -- b
b -- c
b -- d
c -- e
c -- f
a -- g
a -- h
a -- i
a -- j
}
```
$1^7, 3, 4^2$:
```graphviz
graph T7 {
a -- b
b -- c
b -- d
g -- e
g -- f
a -- g
g -- h
a -- i
a -- j
}
```
```graphviz
graph T8 {
a -- b
b -- c
a -- d
g -- e
g -- f
b -- g
g -- h
a -- i
a -- j
}
```
$1^6, 3^4$:
```graphviz
graph T9 {
a -- b
b -- c
c -- d
c -- e
g -- f
b -- g
g -- h
a -- i
a -- j
}
```
```graphviz
graph T10 {
a -- b
b -- c
c -- d
c -- e
g -- f
b -- i
g -- h
a -- g
a -- j
}
```
---
### Naloga 5
Ali ima kateri od grafov s spodnje slike Eulerjev obhod ali sprehod?
Če ne, koliko najmanj potez potrebujemo, da ga lahko narišemo?
```graphviz
graph G1 {
rankdir=LR
a -- b [color=red]
a -- c [color=red]
b -- c [color=red]
b -- d [color=red]
b -- e [color=red]
c -- d [color=red]
c -- f [color=red]
d -- e [color=red]
d -- f [color=red]
e -- f [color=red]
}
```
```graphviz
graph G2 {
rankdir=LR
a -- c [color=red]
a -- d [color=red]
e -- b [color=red]
a -- b [color=red]
b -- h [color=green]
c -- d [color=red]
c -- e [color=red]
d -- f [color=green]
e -- g [color=blue]
f -- g [color=blue]
f -- h [color=green]
g -- h [color=magenta]
}
```
----
1. ${G_1}$:
* ni Eulerjevega obhoda
* Eulerjev sprehod: $ebacbdcfdef$
2. ${G_2}$:
* ni Eulerjevega obhoda ali sprehoda
* poteze: $acdabec$, $bhfd$, $egf$, $gh$
---
### Naloga 6
Kateri od grafov na spodnji sliki imajo Hamiltonov cikel?
```graphviz
graph G1 {
a -- b [color=red]
a -- c [color=red]
a -- d [style=dotted]
b -- e [style=dotted]
b -- j [color=red]
c -- e [color=red]
c -- f [style=dotted]
d -- f [color=red]
d -- k [color=red]
e -- g [color=red]
e -- h [style=dotted]
f -- g [color=red]
f -- i [style=dotted]
h -- i [color=red]
h -- j [color=red]
i -- k [color=red]
j -- k [style=dotted]
}
```
```graphviz
graph G2 {
rankdir=LR
node[style=filled]
b [color=black]
d [color=black]
h [color=black]
a [color=cyan]
c [color=cyan]
e [color=yellow]
f [color=magenta]
g [color=magenta]
i [color=pink]
j [color=pink]
k [color=pink]
a -- b [color=red]
a -- c [color=red]
c -- b [style=dotted]
b -- d [style=dotted]
b -- e [color=red]
e -- d [color=red]
d -- f [color=red]
d -- g [style=dotted]
g -- f [color=red]
c -- h
h -- g [color=red]
b -- i [style=dotted]
d -- j [style=dotted]
i -- h [color=red]
h -- j
i -- j [style=dotted]
i -- k [color=red]
k -- j [color=red]
}
```
```graphviz
graph G3 {
rankdir=LR
a -- b
a -- c
a -- d
b -- e
c -- e
c -- f
d -- f
e -- g
f -- g
g -- h
e -- i
h -- i
h -- j
f -- j
e -- k
f -- l
k -- m
l -- o
b -- m
i -- n
j -- n
k -- n
l -- n
d -- o
m -- p
n -- p
o -- p
}
```
----
1. ${G_1}$: našli smo Hamiltonov cikel
2. ${G_2}$:
- našli smo Hamiltonovo pot
- če odstranimo $3$ vozlišča, graf razpade na $4$ povezane komponente, zato nima Hamiltonovega cikla
3. ${G_3}$: nima Hamiltonove poti - DN
---
### Naloga 7
Ali je graf s spodnje slike Hamiltonov?
```graphviz
graph G {
a -- c
a -- d
b -- c
b -- d
a -- e
a -- f
b -- g
e -- g
f -- g
c -- h
g -- h
d -- i
g -- i
c -- j
e -- j
i -- j
d -- k
f -- k
h -- k
j -- k
}
```
---
### Naloga 8
Ali se lahko šahovski konjiček sprehodi po šahovnici velikosti $3 \times 4$ tako, da vsako polje obišče natanko enkrat in konča tam, kjer je začel? Zapiši kot problem iz teorije grafov in ga reši.
---
### Naloga 9
Pokaži, da ima enostaven kubičen graf na $6$ vozliščih Hamiltonov cikel. S pomočjo te ugotovitve potem poišči vse neizomorfne kubične grafe na največ $6$ vozliščih.
Sign in with Wallet
