Matematické Fórum

Honza789 · 20. 01. 2016 12:55

Potřeboval bych pomoct s jedním příkladem prosím. "Pro která n existuje bipartitní graf na n vrcholech, jehož doplněk je opět bipartitní?" Děkuji předem za odpověď.

vytautas · 20. 01. 2016 14:15

↑ Honza789:

ahoj

graf je bipartitný vtedy, keď sa dá rozdeliť na dve skupiny vrcholov, medzi ktorými nevedie hrana(jednoducho povedané).Čiže sa to dá povedať aj tak, že graf neobsahuje kružnicu $C_3$ .Ak uvažujeme graf na aspoň $5$ vrcholoch, tak aspoň jedna partita má viac ako 2 vrcholy (Dirichletov princíp), čiže v doplnku grafu určite budú tieto 3 vrcholy navzájom pospájané, takže tam vznikne $C_3$ a už určite nebude bipartitný. Takže treba rozobrať prípady len pre menšie ako 5, ak sa teda nemýlim.

Wotton · 20. 01. 2016 15:07 — Editoval Wotton (20. 01. 2016 15:08)

↑ vytautas:

no máš tam nepřesnost. Graf $C_5$ neobsahuje $C_3$ a není bipartitní (platí jen implikace). Ale jinak souhlasím.

Honza789 · 20. 01. 2016 15:18

Dobře, takže když uvažujeme n<5, tak bipartitní graf i jeho doplněk bude když n=2,3,4. Říkám to správně?

Wotton · 20. 01. 2016 15:19 — Editoval Wotton (20. 01. 2016 15:20)

a proč ne i n=1?

jinak souhlas, jen by bylo asi dobré, pro každé n nějaký takový uvést.

Honza789 · 20. 01. 2016 15:23

Nevím, nedokážu si představit v grafu, který má jeden vrchol, dvě partity.

Wotton · 20. 01. 2016 15:32

Nikde není řečeno, že obě musí být neprázdné. Jen pro případ, že je jedna prázdná, tak musí platit $E=\emptyset$ . Což pro n=1 není problém splnit.

Honza789 · 20. 01. 2016 15:43

Dobře, děkuju za pomoc.

Matematické Fórum

#1 20. 01. 2016 12:55

Bipartitní graf

#2 20. 01. 2016 14:15

Re: Bipartitní graf

#3 20. 01. 2016 15:07 — Editoval Wotton (20. 01. 2016 15:08)

Re: Bipartitní graf

#4 20. 01. 2016 15:18

Re: Bipartitní graf

#5 20. 01. 2016 15:19 — Editoval Wotton (20. 01. 2016 15:20)

Re: Bipartitní graf

#6 20. 01. 2016 15:23

Re: Bipartitní graf

#7 20. 01. 2016 15:32

Re: Bipartitní graf

#8 20. 01. 2016 15:43

Re: Bipartitní graf

Zápatí