Matematické Fórum

OrangeTree

Hezký novoroční večer :),

chtěla bych dokázat, že kartézským součinem dvou bipartitních grafů vznikne opět bipartitní graf.

Řekněme, že mám dva bipartitní grafy $G$ a $H$ , kde $V(G) = A \cup B$ a $V(H) = C \cup D$ . S tím, že množina $A$ je množina vrcholů 1. barvy a množina $B$ je množina vrcholů 2. barvy. Obdobně u množin $C$ a $D$ .

Množina vrcholů kartézského součinu: $V(G \times H) = (A \times B) \cup (A \times D) \cup (B \times C) \cup (B \times D)$ .

Vrcholy z množiny $(A \times C)$ mohou sousedit s vrcholy z množin $(A \times D)$ a $(B \times C)$ , jednou "zafixuji" první souřadnici, v dalším případě druhou souřadnici.

Takto zjistím, že mezi množinami $(A \times C)$ a $(B \times D)$ neexistuje hrana, tedy je mohu obarvit první barvou. Obdobně mezi množinami $(A \times D)$ a $(B \times C)$ neexistuje hrana, tedy je mohu obarvit druhou barevnou.

Je to takhle korektní :)?

Brano · 06. 01. 2015 10:13

no je spravne to co tvrdis, t.j. ze ten graf mozes rozdelit na $P=A\times C\cup B\times D$ a $Q=B\times C\cup A\times D$ ale to tvoje zdovodnenie je tak trochu nezrozumitelne - ja by som ako vyucujuci vyzadoval trochu formalnejsi sposob vyjadrovania; napr. takto:

predpokladajme, ze 2 rozne vrcholy v $P$ su susedne t.j. bud

a) $(a,c)\in A\times C$ susedi s $(b,d)\in B\times D$ - potom ale by platilo bud $a=b$ alebo $c=d$ lenze ani jedno nemoze nastat

alebo

b) $(a_1,c_1)\in A\times C$ susedi s $(a_2,c_2)\in A\times C$ - potom bud $a_1=a_2$ a $c_1$ susedi s $c_2$ - co znova nemoze nastat, lebo $C$ je jedna z "polovic" bipartitnrho grafu; alebo $c_1=c_2$ a $a_1$ susedi s $a_2$ - co nemoze nastat s obdobneho dovodu

alebo

c) $(b_1,d_1)\in B\times D$ susedi s $(b_2,d_2)\in B\times D$ - co nemoze nastat analogicky ako pre pripad b)

teda ziadne 2 vrcholy v $P$ nemozu byt susedne a rovnaky argumen je aj pre to, ze ziadne 2 vrcholy v $Q$ nemozu byt susedne. QED.

Matematické Fórum

#1 01. 01. 2015 20:03 — Editoval OrangeTree (01. 01. 2015 21:39)

Teorie grafů: Kartézský součin bipartitních grafů je opět bipartitní

#2 06. 01. 2015 10:13

Re: Teorie grafů: Kartézský součin bipartitních grafů je opět bipartitní

Zápatí