Diskretne strukture (FiM) - vaje 16.12.2020

--- tags: vaje, ds, grafi hackmd: https://hackmd.io/kp5X-grpQt2HzB4OZa6oLg plugins: mathjax, viz.js --- # 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$ ```graphviz graph G { a } ``` #### 2 vozlišči $\overline{K_2}$ ```graphviz graph G1 { a b } ``` $K_2 \cong P_1$ ```graphviz graph G2 { rankdir=LR a -- b } ``` #### 3 vozlišča 0, 0, 0: $\overline{K_3}$ ```graphviz graph G1 { a b c } ``` 0, 1, 1: $K_2 + K_1 \cong \overline{P_2}$ ```graphviz graph G2 { a -- c b } ``` 1, 1, 2: $P_2$ ```graphviz graph G3 { rankdir=LR a -- b -- c } ``` 2, 2, 2: $K_3 \cong C_3$ ```graphviz graph G4 { rankdir=LR a -- b -- c -- a } ``` #### 4 vozlišča 0, 0, 0, 0: $\overline{K_4}$ ```graphviz graph G1 { a b c d } ``` 0, 0, 1, 1: $K_2 + 2K_1$ ```graphviz graph G2 { a -- b c d } ``` 0, 1, 1, 2: $P_2 + K_1$ ```graphviz graph G3 { rankdir=LR a -- b -- c d } ``` 1, 1, 1, 1: $2K_2$ ```graphviz graph G4 { a -- b c -- d } ``` 0, 2, 2, 2: $K_3 + K_1$ ```graphviz graph G5 { rankdir=LR a -- b -- c -- a d } ``` 1, 1, 1, 3: $\overline{K_3 + K_1}$ ```graphviz graph G6 { a -- b a -- c a -- d } ``` 1, 1, 2, 2: $P_3 \cong \overline{P_3}$ ```graphviz graph G7 { rankdir=LR a -- b -- c -- d } ``` 2, 2, 2, 2: $C_4$ ```graphviz graph G8 { rankdir=LR a -- b -- c -- d -- a } ``` 1, 2, 2, 3: $\overline{K_3 + K_1}$ ```graphviz graph G9 { rankdir=LR a -- b -- c a -- c a -- d } ``` 2, 2, 3, 3: $\overline{K_2 + 2K_1}$ ```graphviz graph G10 { rankdir=LR a -- b -- c -- d -- b c -- a } ``` 3, 3, 3, 3: $K_4$ ```graphviz 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$: ```graphviz graph G { rankdir=LR 1 -- 2 -- 3 -- 4 -- 5 2 -- 4 2 -- 5 } ``` $\overline{G}$: ```graphviz 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$: ```graphviz graph G1 { rankdir=LR a -- d b -- e d -- c -- e d -- e } ``` ```graphviz 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$: ```graphviz graph G2 { rankdir=LR a -- e -- b -- c -- d -- e } ``` ```graphviz graph G2kom { rankdir=LR a -- b -- d a -- c -- e a -- d } ``` Grafa nista izomorfna! - $2, 2, 2, 2, 2$: ```graphviz graph G3 { rankdir=LR a -- b -- c -- d -- e -- a } ``` ```graphviz 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 ```graphviz graph G1 { rankdir=LR a b c -- d -- e -- c } ``` 0, 1, 1, 1, 3 ```graphviz graph G2 { a b -- e c -- e d -- e } ``` 0, 1, 1, 2, 2 ```graphviz graph G3 { rankdir=LR a b -- c -- d -- e } ``` 1, 1, 1, 1, 2 ```graphviz graph G4 { rankdir=LR a -- b c -- e -- d } ``` Grafi na $5$ vozliščih s $7$ povezavami: ```graphviz graph G1kom { rankdir=LR a -- b a -- c a -- d a -- e b -- c b -- d b -- e } ``` ```graphviz graph G2kom { rankdir=LR a -- b a -- c a -- d a -- e b -- c -- d -- b } ``` ```graphviz graph G3kom { rankdir=LR a -- b a -- c a -- d a -- e b -- d b -- e c -- e } ``` ```graphviz 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. ```graphviz graph G { rankdir=LR a -- b a -- c b -- c b -- d } ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.