Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 10.12.2020

---

Urejenosti

Delna urejenost $(A, \le)$, podmnožica $B \subseteq A$

• supremum: $x = \sup B \iff \forall y \in B: y \le x \land \forall z \in A: (\forall y \in B: y \le z \Rightarrow x \le z)$
• infimum: $x = \inf B \iff \forall y \in B: x \le y \land \forall z \in A: (\forall y \in B: z \le y \Rightarrow z \le x)$

---

Naloga 1

Na $\mathbb{R}^2$ definiramo relacijo $\preceq$ takole:

\[(x_1,y_1)\preceq(x_2,y_2) \Leftrightarrow x_1 \leq x_2 {\rm\;in\;} y_1 \leq y_2.\]

1. Pokaži, da je $(\mathbb{R}^2, \preceq)$ delna urejenost.
2. Določi supremum in infimum elementov $(1,3)$ in $(2,4)$ ter supremum in infimum elementov $(3,2)$ in $(4,1)$.

---

1. • Refleksivnost: $(x_1, y_1) \preceq (x_1, y_1) \iff x_1 \le x_1 \land y_1 \le y_1$ velja

   • Antisimetričnost:

     \[\begin{aligned} (x_1, y_1) \preceq (x_2, y_2) \land (x_2, y_2) \preceq (x_1, y_1) &\Rightarrow x_1 \le x_2 \land y_1 \le y_2 \land x_2 \le x_1 \land y_2 \le y_1 \\ &\Rightarrow x_1 = x_2 \land y_1 = y_2 \\ &\Rightarrow (x_1, y_1) = (x_2, y_2) \end{aligned}\]

   • Tranzitivnost:

     \[\begin{aligned} (x_1, y_1) \preceq (x_2, y_2) \land (x_2, y_2) \preceq (x_3, y_3) &\Rightarrow x_1 \le x_2 \land y_1 \le y_2 \land x_2 \le x_3 \land y_2 \le y_3 \\ &\Rightarrow x_1 \le x_3 \land y_1 \le y_3 \\ &\Rightarrow (x_1, y_1) \preceq (x_3, y_3) \end{aligned}\]
2. • $\sup\lbrace (1, 3), (2, 4) \rbrace = (2, 4)$
   • $\inf\lbrace (1, 3), (2, 4) \rbrace = (1, 3)$
   • $\sup\lbrace (3, 2), (4, 1) \rbrace = (4, 2)$
   • $\inf\lbrace (3, 2), (4, 1) \rbrace = (3, 1)$
   • $\sup\lbrace (x_1, y_1), (x_2, y_2) \rbrace = (\max\lbrace x_1, x_2 \rbrace, \max\lbrace y_1, y_2 \rbrace)$
   • $\inf\lbrace (x_1, y_1), (x_2, y_2) \rbrace = (\min\lbrace x_1, x_2 \rbrace, \min\lbrace y_1, y_2 \rbrace)$

---

Teorija grafov

(Neusmerjen) graf $G = (V, E)$

• $V$ … množica vozlišč
• $E \subseteq {V \choose 2} = \lbrace \lbrace u, v \rbrace \mid u, v \in V \land u \ne v \rbrace$ … množica povezav

graph G {
  a -- b
  a -- c
  b -- c
  a -- d
  c -- d
  b -- e
  e -- f
  f -- d
  a -- g
  c -- g
  f -- g
}

• stopnja vozlišča $u$: $d_G(u) = d(u) = |\lbrace e \in E \mid u \in e \rbrace|$
• maksimalna stopnja grafa $G$: $\Delta = \max_{u \in V} d_G(u)$
• minimalna stopnja grafa $G$: $\delta = \min_{u \in V} d_G(u)$
• graf je regularen, če imajo vsa vozlišča enako stopnjo
• graf je dvodelen, če lahko zapišemo $V = A + B$, tako da velja, da za vsako povezavo $\lbrace u, v \rbrace \in E$ velja $u \in A$ in $v \in B$

• grafa $G_1 = (V_1, E_1)$ in $G_2 = (V_2, E_2)$ sta izomorfna, če obstaja bijektivna preslikava $f : V_1 \to V_2$, za katero velja

  \[\forall u, v \in V_1: (\{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2)\]

---

Naloga 2

Dan je graf $G=(V,E)$, kjer je $V = \lbrace 1,2,3,4,5 \rbrace$ in $E = \lbrace \lbrace 1,2 \rbrace, \lbrace 1,4 \rbrace, \lbrace 1,5 \rbrace, \lbrace 2,3 \rbrace, \lbrace 2,4 \rbrace, \lbrace 3,4 \rbrace, \lbrace 4,5 \rbrace \rbrace$.

1. Čim lepše nariši graf $G$.
2. Poišči stopnje vseh vozlišč ter minimalno in maksimalno stopnjo grafa $G$. Ali je graf regularen?
3. Ali je graf dvodelen?

---

1. graph G {
   1 -- 2
   1 -- 4
   1 -- 5
   2 -- 3
   2 -- 4
   3 -- 4
   4 -- 5
   }
   

2. • $d(1) = 3$
   • $d(2) = 3$
   • $d(3) = 2$
   • $d(4) = 4$
   • $d(5) = 2$
   • $\Delta(G) = 4$
   • $\delta(G) = 2$
   • zaporedje stopenj: $2, 2, 3, 3, 4$
   • graf ni regularen
3. Graf ni dvodelen, saj vsebuje lihe cikle (trikotniki, petkotnik).

---

Naloga 3

Na zabavi se je zbralo $13$ ljudi. Vsak je s seboj prinesel $3$ darila, ki bi jih rad izmenjal s tremi drugimi udeleženci zabave. Ali je to izvedljivo? Predstavi kot problem iz teorije grafov in ga reši.

---

• $G = (V, E)$
• $V$ … udeleženci, $|V| = 13$
• $\lbrace u, v \rbrace \in E$, če si $u$ in $v$ izmenjata darilo
• graf je $3$-regularen: $d_G(u) = 3$ za vse $u \in V$
• lema o rokovanju: $\sum_{u \in V} d_G(u) = 2 |E|$
• $|E| = {13 \cdot 3 \over 2} = 19.5$
• ni izvedljivo

---

Naloga 4

Ali sta spodnja grafa izomorfna?

---

• $|V_1| = |V_2| = 5$
• $|E_1| = |E_2| = 8$
• zaporedje stopenj:
  • $G_1$: 2, 3, 3, 4, 4
  • $G_2$: 3, 3, 3, 3, 4
  • grafa nista izomorfna

---

Naloga 5

Ali sta spodnja grafa izomorfna?

---

• $|V_1| = |V_2| = 8$
• $|E_1| = |E_2| = 12$
• grafa sta $3$-regularna
• izomorfizem:
  • $a \to 1$
  • $b \to 2$
  • $c \to 3$
  • $e \to 5$
  • $g \to 7$
  • $h \to 8$
  • $d \to 4$
  • $f \to 6$
• grafa sta izomorfna

---

Naloga 6

Ali sta spodnja grafa izomorfna? Nasvet: v vsakem od grafov preštej cikle dolžine $4$.

---

• $|V_1| = |V_2| = 12$
• grafa sta $3$-regularna
• cikli dolžine $4$:
  • $G_1$: abce, adge, bcfi, dgjk, fhli, hjkl, 6 ciklov
  • $G_2$: (1, 2, 3, 5); (1, 4, 7, 5); (6, 8, 12, 9); (8, 10, 11, 12); 4 cikli
  • grafa nista izomorfna

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.