Diskretne strukture (FiM) - vaje 17.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} \cong 2K_1\)

graph G1 {
  a
  b
}

\(K_2 \cong P_1\)

graph G2 {
  rankdir=LR
  a -- b
}

3 vozlišča

\(\overline{K_3} \cong 3K_1\)

graph G1 {
  a
  b
  c
}

\(K_2 + K_1 \cong \overline{P_2}\)

graph G2 {
  a -- c
  b
}

\(P_2\)

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

\(K_3 \cong C_3\)

graph G4 {
  rankdir=LR
  a -- c -- b -- 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 \cong \overline{C_4}\)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
  2 -- 4
  2 -- 5
  3 -- 4 -- 5
}

\(\overline{G}\):

graph G {
  rankdir=LR
  1 -- 3
  1 -- 4
  1 -- 5
  3 -- 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
  ​​  e -- b
  ​​  e -- c
  ​​  e -- d
  ​​  c -- d
  ​​}
  

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

  Izomorfizem:

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

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

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

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

  Grafa nista izomorfna (en ima 3-cikel, drugi pa ne).

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

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

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

  Grafa sta 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.

Grafi na 5 vozliščih s 3 povezavami:

0, 0, 2, 2, 2

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

0, 1, 1, 1, 3

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

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 -- d -- e
}

Komplementi: 7 povezav

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

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
  c -- e -- b -- d
}

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

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.

• \((1 \Rightarrow 2)\)

• \((2 \Rightarrow 3)\)

• \((3 \Rightarrow 1)\)

  • predpostavka: \(G\) ne vsebuje lihega cikla
  • dokazujemo, da \(V = A + B\), tako da za vsako \(\lbrace u, v \rbrace \in E\) velja \(u \in A\), \(v \in B\)
  • izberemo vozlišče \(u_0 \in V\), naj bo \(u_0 \in A\)
  • za vsako \(\lbrace u, v \rbrace \in E\) z \(u \in A\) naj bo \(v \in B\)
  • za vsako \(\lbrace u, v \rbrace \in E\) z \(u \in B\) naj bo \(v \in A\)
  • ker nimamo lihih ciklov, sta množici \(A\) in \(B\) disjunktni
  • torej je graf \(G\) dvodelen

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
}