Diskretne strukture (FiM) - vaje 9.12.2020

Urejenosti

Delna urejenost \((A, \le)\)

• \(x\) infimum množice \(B \subseteq A\):

  \[ 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) \]

• \(x\) supremum množice \(B \subseteq A\):

  \[ 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) \]

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\) je množica vozlišč
• \(E \subseteq {V \choose 2} = \lbrace \lbrace u, v \rbrace \mid u, v \in V, u \ne v \rbrace\) je množica povezav

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

• Stopnja vozlišča \(u \in V\): \(d_G(u) = d(u) = |\lbrace e \in E \mid u \in e \rbrace|\)

• Maksimalna stopnja grafa \(\Delta(G) = \max_{u \in V} d_G(u)\)

• Minimalna stopnja grafa \(\delta(G) = \min_{u \in V} d_G(u)\)

• Graf je dvodelen, če lahko zapišemo \(V = A + B\), tako da za vsako povezavo \(\lbrace u, v \rbrace \in E\) velja \(u \in A\), \(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\), tako da 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. • \(\delta(G) = 2\)
   • \(\Delta(G) = 4\)
   • 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 zabave, \(|V| = 13\)
• \(\lbrace u, v \rbrace \in E\) … \(u\) in \(v\) si izmenjata darilo
• \(d_G(u) = 3\) za vse \(u \in V\)

Lema o rokovanju: \(\sum_{u \in V} d_G(u) = 2 |E|\)

• \(39 = \sum_{u \in V} d_G(u) = 2 |E|\)
• \(|E| = 19.5\) protislovje

To torej ni izvedljivo.

Naloga 4

Ali sta spodnja grafa izomorfna?

• \(|V_1| = |V_2| = 5\)
• \(|E_1| = |E_2| = 8\)
• stopnje vozlišč - 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\)
• oba grafa sta \(3\)-regularna
• izomorfizem:
  • \(a \to 1\)
  • \(b \to 2\)
  • \(c \to 3\)
  • \(e \to 5\)
  • \(f \to 6\)
  • \(g \to 7\)
  • \(d \to 4\)
  • \(h \to 8\)
• 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\)
• oba grafa sta \(3\)-regularna
• cikli dolžine \(4\):
  • \(G_1\): 6 ciklov dolžine 4
    • abce
    • adge
    • bcfi
    • dgjk
    • fhli
    • hjkl
  • \(G_2\): 4 cikli dolžine 4
    • 1, 2, 3, 5
    • 1, 4, 7, 5
    • 6, 8, 12, 9
    • 8, 10, 11, 12
  • grafa nista izomorfna