Diskretne strukture (FiM) - vaje 16.12.2020

Teorija grafov

Naloga 1

Poišči vse neizomorfne enostavne grafe na treh ali štirih vozliščih.

0 vozlišč

\(K_0 \cong G = (\emptyset, \emptyset)\)

1 vozlišče

\(K_1 \cong P_0\)

graph G {
  a
}

2 vozlišči

\(\overline{K_2}\)

graph G1 {
  a
  b
}

\(K_2 \cong P_1\)

graph G2 {
  rankdir=LR
  a -- b
}

3 vozlišča

0, 0, 0: \(\overline{K_3}\)

graph G1 {
  a
  b
  c
}

0, 1, 1: \(K_2 + K_1 \cong \overline{P_2}\)

graph G2 {
  a -- c
  b
}

1, 1, 2: \(P_2\)

graph G3 {
  rankdir=LR
  a -- b -- c
}

2, 2, 2: \(K_3 \cong C_3\)

graph G4 {
  rankdir=LR
  a -- b -- c -- a
}

4 vozlišča

0, 0, 0, 0: \(\overline{K_4}\)

graph G1 {
  a
  b
  c
  d
}

0, 0, 1, 1: \(K_2 + 2K_1\)

graph G2 {
  a -- b
  c
  d
}

0, 1, 1, 2: \(P_2 + K_1\)

graph G3 {
  rankdir=LR
  a -- b -- c
  d
}

1, 1, 1, 1: \(2K_2\)

graph G4 {
  a -- b
  c -- d
}

0, 2, 2, 2: \(K_3 + K_1\)

graph G5 {
  rankdir=LR
  a -- b -- c -- a
  d
}

1, 1, 1, 3: \(\overline{K_3 + K_1}\)

graph G6 {
  a -- b
  a -- c
  a -- d
}

1, 1, 2, 2: \(P_3 \cong \overline{P_3}\)

graph G7 {
  rankdir=LR
  a -- b -- c -- d
}

2, 2, 2, 2: \(C_4\)

graph G8 {
  rankdir=LR
  a -- b -- c -- d -- a
}

1, 2, 2, 3: \(\overline{K_3 + K_1}\)

graph G9 {
  rankdir=LR
  a -- b -- c
  a -- c
  a -- d
}

2, 2, 3, 3: \(\overline{K_2 + 2K_1}\)

graph G10 {
  rankdir=LR
  a -- b -- c -- d -- b
  c -- a
}

3, 3, 3, 3: \(K_4\)

graph G11 {
  rankdir=LR
  a -- b -- c -- d -- b
  c -- a -- d
}

Naloga 2

Poišči komplement grafa \(G=(V,E)\), kjer je

\[ \begin{aligned} V &= \{1,2,3,4,5\} \quad \text{in} \\ E &= \{\{1,2\},\{2,3\}, \{2,4\},\{2,5\},\{3,4\},\{4,5\}\}. \end{aligned} \]

• Komplement grafa \(G = (V, E)\) je graf \(\overline{G} = (V, \overline{E})\), kjer je \(\overline{E} = {V \choose 2} \setminus E\)
• \(\overline{E} = \lbrace \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 1, 5 \rbrace, \lbrace 3, 5 \rbrace \rbrace\)

\(G\):

graph G {
  rankdir=LR
  1 -- 2 -- 3 -- 4 -- 5
  2 -- 4
  2 -- 5
}

\(\overline{G}\):

graph Gkom {
  rankdir=LR
  1 -- 3 -- 5
  1 -- 4
  1 -- 5
  2
}

Naloga 3

Poišči vse enostavne grafe na \(5\) vozliščih, ki so izomorfni svojemu komplementu.

• \(|V| = 5\)
• \(|E| = |\overline{E}| = {5 \choose 2}/2 = 5\)
• zaporedje stopenj: \(a, b, 2, 4-b, 4-a\)

• \(0, b, 2, 4-b, 4\): ni mogoče

• \(1, 1, 2, 3, 3\):

  ​​graph G1 {
  ​​  rankdir=LR
  ​​  a -- d
  ​​  b -- e
  ​​  d -- c -- e
  ​​  d -- e
  ​​}
  

  ​​graph G1kom {
  ​​  rankdir=LR
  ​​  a -- b
  ​​  a -- c
  ​​  a -- e
  ​​  c -- b -- d
  ​​}
  

  Izomorfizem:

  • \(a \to d\)
  • \(b \to e\)
  • \(c \to c\)
  • \(d \to b\)
  • \(e \to a\)

• \(1, 2, 2, 2, 3\):

  ​​graph G2 {
  ​​  rankdir=LR
  ​​  a -- e -- b -- c -- d -- e
  ​​}
  

  ​​graph G2kom {
  ​​  rankdir=LR
  ​​  a -- b -- d
  ​​  a -- c -- e
  ​​  a -- d
  ​​}
  

  Grafa nista izomorfna!

• \(2, 2, 2, 2, 2\):

  ​​graph G3 {
  ​​  rankdir=LR
  ​​  a -- b -- c -- d -- e -- a
  ​​}
  

  ​​graph G3kom {
  ​​  rankdir=LR
  ​​  a -- c -- e -- b -- d -- a
  ​​}
  

  Opazimo, da sta grafa izomorfna.

Naloga 4

Poišči vse neizomorfne enostavne grafe na \(5\) vozliščih s \(7\) povezavami.

Nasvet: dva grafa sta izomorfna natanko tedaj, ko sta izomorfna njuna komplementa.

Komplementi: \(3\) povezave

0, 0, 2, 2, 2

graph G1 {
  rankdir=LR
  a
  b
  c -- d -- e -- c
}

0, 1, 1, 1, 3

graph G2 {
  a
  b -- e
  c -- e
  d -- e
}

0, 1, 1, 2, 2

graph G3 {
  rankdir=LR
  a
  b -- c -- d -- e
}

1, 1, 1, 1, 2

graph G4 {
  rankdir=LR
  a -- b
  c -- e -- d
}

Grafi na \(5\) vozliščih s \(7\) povezavami:

graph G1kom {
  rankdir=LR
  a -- b
  a -- c
  a -- d
  a -- e
  b -- c
  b -- d
  b -- e
}

graph G2kom {
  rankdir=LR
  a -- b
  a -- c
  a -- d
  a -- e
  b -- c -- d -- b
}

graph G3kom {
  rankdir=LR
  a -- b
  a -- c
  a -- d
  a -- e
  b -- d
  b -- e
  c -- e
}

graph G4kom {
  rankdir=LR
  a -- c -- b
  a -- d -- b
  a -- e -- b
  c -- d
}

Naloga 5

Pokaži, da so naslednje trditve ekvivalentne:

1. Graf je dvodelen.
2. Graf je 2-obarvljiv (vozlišča lahko pobarvamo z dvema barvama tako, da sosednji dve nista enako obarvani).
3. Graf ne vsebuje lihega cikla.

\(G = (V, E)\)

• \((1 \Rightarrow 2)\)

  • predpostavka: \(V = A + B\), \(\forall \lbrace u, v \rbrace \in E: (u \in A \land v \in B)\)
  • iščemo \(c : V \to 2\), tako da za vsak \(\lbrace u, v \rbrace \in E\) velja \(c(u) \ne c(v)\)
  • \(c(u) = 0\) če \(u \in A\), \(c(v) = 1\) če \(v \in B\)

• \((2 \Rightarrow 3)\)

  • predpostavka: imamo \(c : V \to 2\), tako da za vsak \(\lbrace u, v \rbrace \in E\) velja \(c(u) \ne c(v)\)
  • recimo, da graf ima lih cikel \(u_1 u_2 \dots u_n\) za nek lih \(n\)
  • potem \(c(u_1) = c(u_n)\), toda \(\lbrace u_1, u_n \rbrace \in E\), protislovje
  • torej graf nima lihih ciklov

• \((3 \Rightarrow 1)\)

Naloga 6

Za spodnji graf preštej število podgrafov in število induciranih podgrafov.

graph G {
  rankdir=LR
  a -- b
  a -- c
  b -- c
  b -- d
}