Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 6.1.2021

---

Teorija grafov

Drevesa: povezani grafi brez ciklov

• $T = (V, E)$
• $|E| = |V| - 1$

Poln dvodelen graf ${K_{m,n}} = (V, E)$

• $V = A + B$, $|A| = m$, $|B| = n$
• $E = \lbrace \lbrace u, v \rbrace \mid u \in A, v \in B \rbrace$

Primer ${K_{2,3}}$

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

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$

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.

---

• $|E| = |V| - 1 = 16$
• $x$ … št. vozlišč stopnje 4
• Lema o rokovanju: $\sum_{u \in V(T)} {d_T}(u) = x \cdot 4 + (17-x) \cdot 1 = 2|E| = 32$
• $3x = 15$
• $x = 5$

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)$

• $|V| = 10$
• $|E| = 9$
• $\forall u \in V: {d_T}(u) \ne 2$

$1^9, 9$:

graph T1 {
  a -- b
  a -- c
  a -- d
  a -- e
  a -- f
  a -- g
  a -- h
  a -- i
  a -- j
}

$1^8, 3, 7$:

graph T2 {
  a -- b
  b -- c
  b -- d
  a -- e
  a -- f
  a -- g
  a -- h
  a -- i
  a -- j
}

$1^8, 4, 6$:

graph T3 {
  a -- b
  b -- c
  b -- d
  b -- e
  a -- f
  a -- g
  a -- h
  a -- i
  a -- j
}

$1^8, 5^2$:

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$:

graph T5 {
  a -- b
  b -- c
  b -- d
  g -- e
  g -- f
  a -- g
  a -- h
  a -- i
  a -- j
}

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$:

graph T7 {
  a -- b
  b -- c
  b -- d
  g -- e
  g -- f
  a -- g
  g -- h
  a -- i
  a -- j
}

graph T8 {
  a -- b
  b -- c
  a -- d
  g -- e
  g -- f
  b -- g
  g -- h
  a -- i
  a -- j
}

$1^6, 3^4$:

graph T9 {
  a -- b
  b -- c
  c -- d
  c -- e
  g -- f
  b -- g
  g -- h
  a -- i
  a -- j
}

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?

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]
}

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?

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]
}

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]
}

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?

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.

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.