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.