Diskretne strukture (FiM)

« nazaj

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
}

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.