Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 13.1.2021


Teorija grafov


Naloga 1

Za spodnje grafe ugotovi, ali so ravninski.


  1. graph G1 {
      rankdir=LR
      a -- b -- c -- d -- h --g -- f
      a -- e -- f
      e -- b -- f -- c -- g -- d
      a -- f
      b -- g
      c -- h
    }
    

    Graf je ravninski.

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

    Graf ni ravninski, ima minor ${K_5}$:

    graph G2kontrakt {
      eadh -- b
      eadh -- c
      eadh -- f
      eadh -- g
      b -- c
      b -- f
      b -- g
      c -- f
      c -- g
      f -- g
    }
    
  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, ima minor ${K_{3, 3}}$:

    graph G3kontrkat {
      ab -- c
      ab -- h
      ab -- ef
      d -- c
      d -- h
      d -- ef
      g -- c
      g -- h
      g -- ef
    }
    

Naloga 2

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



Naloga 3

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



Naloga 4

Naj bo $G$ 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$?



Naloga 5

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

graph G1 {
  rankdir=LR
  node [style=filled]
  
  a [color=red]
  b [color=green]
  c [color=blue]
  d [color=blue]
  e [color=green]

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

Barvnost: 3 (imamo lih cikel, našli smo 3-barvanje)

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

  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]

  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
}

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

Barvnost je 4 (ima 4-kliko, našli smo 4-barvanje)

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
}