Diskretne strukture (FiM)

« nazaj

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
}

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.