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}\]

$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.



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)$


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
}