Diskretne strukture (FiM) - vaje 14.1.2021

Teorija grafov

  • Graf \(G = (V, E)\) je ravninski, če obstaja vložitev v ravnino (tj., povezave se ne sekajo).
  • Graf ni ravninski natanko tedaj, ko ima minor \({K_5}\) ali \({K_{3, 3}}\) (tj., tak graf dobimo s krčenjem povezav ter odstranjevanjem vozlišč in povezav).
  • \(v - e + f = 2\), kjer je \(v\) število vozlišč, \(e\) število povezav in \(f\) število lic
    • velja za povezane grafe
    • v splošnem: \(v - e + f = 1 +\) število povezanih komponent

Naloga 1

Za spodnje grafe ugotovi, ali so ravninski.

  1. Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  2. Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  3. Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  4. Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More → 
  1. ​​​graph G1 {
​​​  rankdir=LR
​​​  a -- b -- c -- d -- h -- g -- f -- e -- a
​​​  a -- f -- b -- g -- c -- h
​​​  e -- b
​​​  f -- c
​​​  g -- d
​​​}

    Graf je ravninski.

  2. ​​​graph G2 {
​​​  rankdir=LR
​​​  a -- b -- c -- d -- h -- g -- f -- e -- a
​​​  a -- f -- b -- g -- c -- h
​​​  e -- b
​​​  f -- c
​​​  g -- d
​​​  a -- d
​​​}

    Graf ni ravninski - dokaz za DN.

  3. ​​​graph G3 {
​​​  rankdir=LR
​​​  node [style=filled]
​​​  a [color=red]
​​​  b [color=red]
​​​  e [color=green]
​​​  f [color=green]
​​​  c [color=blue]
​​​  d [color=cyan]
​​​  g [color=magenta]
​​​  h [color=yellow]
​​​  
​​​  a -- b [color=red]
​​​  b -- c -- d -- e
​​​  e -- f  [color=green]
​​​  f -- g -- h -- a
​​​  a -- e
​​​  b -- f
​​​  c -- g
​​​  d -- h
​​​}

    Graf ni ravninski, ker ima minor \({K_{3, 3}}\):

    ​​​graph G3kontrakt {
​​​  ab -- c
​​​  ab -- ef
​​​  ab -- h
​​​  d -- c
​​​  d -- ef
​​​  d -- h
​​​  g -- c
​​​  g -- ef
​​​  g -- h
​​​}

  4. ​​​graph G4 {
​​​  node [style=filled]
​​​  
​​​  e [color=red]
​​​  b [color=red]
​​​  d [color=red]
​​​  f [color=red]
​​​  h [color=red]
​​​  j [color=red]
​​​  a [color=green]
​​​  c [color=blue]
​​​  g [color=cyan]
​​​  i [color=yellow]
​​​  
​​​  a -- c -- g -- i -- a -- g -- e -- c -- i
​​​  b -- d -- h -- j -- b -- h -- f -- d -- j
​​​  a -- b
​​​  e -- f
​​​  i -- j
​​​}

    Graf ni ravninski, ker ima minor \({K_5}\):

    ​​​graph G4kontrakt {
​​​  ebdfhj -- a
​​​  ebdfhj -- c
​​​  ebdfhj -- g
​​​  ebdfhj -- i
​​​  a -- c
​​​  a -- g
​​​  a -- i
​​​  c -- g
​​​  c -- i
​​​  g -- i
​​​}

Naloga 2

Pokaži, da ima povezan kubičen graf v ravnini, pri katerem so vsa lica petkotniki ali šestkotniki, natanko \(12\) petkotnikov.

  • \(v - e + f = 2\)
  • \(3v = 2e = 5a + 6b\), kjer je \(a\) število petkotnikov in \(b\) število šestkotnikov
  • \(f = a + b\)
  • \({5a + 6b \over 3} - {5a + 6b \over 2} + a + b = 2\)
  • \(-{5a + 6b \over 6} + a + b = 2\)
  • \(a = 12\)

Naloga 3

Naj bo \(G\) enostaven graf, ki ima \(11\) vozlišč. Pokaži, da potem \(G\) ni ravninski ali pa njegov komplement ni ravninski.

  • \(v = 11\)
  • Predpostavimo, da sta tako \(G\) kot \(\overline{G}\) ravninska grafa.
  • \(v - e + f \ge 2\)
  • \(v - \overline{e} + \overline{f} \ge 2\)
  • \(3f \le 2e\)
  • \(3\overline{f} \le 2\overline{e}\)
  • \(e + \overline{e} = 55\)
  • \(2v - e - \overline{e} + f + \overline{f} \ge 4\)
  • \(22 - 55 + f + \overline{f} \ge 4\)
  • \(f + \overline{f} \ge 37\)
  • \(f + \overline{f} \le {2 \over 3} (e + \overline{e}) = 36 {2 \over 3}\)
  • Dobimo protislovje, torej \(G\) in \(\overline{G}\) ne moreta biti oba ravninska.

Naloga 4

Naj bo \(G\) povezan regularen graf stopnje \(p \ge 3\), vložen v ravnino tako, da imajo vsa lica enako število povezav \(q \ge 3\) na robu. Kakšna sta lahko \(p\) in \(q\)?

  • \(v - e + f = 2\)
  • \(pv = 2e = qf\)
  • \({2e \over p} - e + {2e \over q} = 2\)
  • \(e ({2 \over p} + {2 \over q} - 1) = 2\)
  • Rešitve:
    • \(p = 3\): \({2 \over q} > {1 \over 3}\)
      • \((p, q) = (3, 3)\): \(e = 6\), \(v = 4\), \(f = 4\), tetraeder
      • \((p, q) = (3, 4)\): \(e = 12\), \(v = 8\), \(f = 6\), kocka
      • \((p, q) = (3, 5)\): \(e = 30\), \(v = 20\), \(f = 12\), dodekaeder
    • \(p = 4\): \({2 \over q} > {1 \over 2}\)
      • \((p, q) = (4, 3)\): \(e = 12\), \(v = 6\), \(f = 8\), oktaeder
    • \(p = 5\): \({2 \over q} > {3 \over 5}\)
      • \((p, q) = (5, 3)\): \(e = 30\), \(v = 12\), \(f = 20\), ikozaeder

Naloga 5

Za grafe na spodnji sliki poišči njihovo barvnost.

graph G1 {
  rankdir=LR
  node [style=filled]

  a -- b
  a -- c
  b -- c
  b -- d
  c -- e
  d -- e

  a [color=red]
  b [color=green]
  c [color=blue]
  d [color=red]
  e [color=green]
}

Bravnost grafa je \(3\) (ima \(3\)-cikel, našli smo \(3\)-barvanje).

graph G2 {
  rankdir=LR
  node [style=filled]

  d -- e
  e -- b
  e -- i
  d -- a
  b -- a
  b -- f
  i -- f
  i -- k
  d -- k
  a -- c
  f -- c
  f -- j
  k -- j
  c -- g
  j -- g
  a -- h
  k -- h
  g -- h

  a [color=red]
  b [color=green]
  c [color=green]
  d [color=green]
  h [color=green]
  e [color=red]
  f [color=red]
  g [color=red]
  k [color=red]
  i [color=green]
  j [color=green]
}

Barvnost grafa je \(2\) (graf je dvodelen).

graph G3 {
  rankdir=LR
  node [style=filled]

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

graph G4 {
  node [style=filled]

  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
  
  a [color=red]
  c [color=green]
  j [color=red]
  k [color=green]
  d [color=blue]
  b [color=red]
  i [color=green]
  f [color=blue]
  e [color=blue]
  h [color=blue]
  g [color=magenta]
}

Graf ima \(5\)-cikel, zato potrebujemo vsaj \(3\) barve, vendar s \(3\) barvami ni šlo, našli smo \(4\)-barvanje. Barvnost grafa je \(4\).

Select a repo