Matematické Fórum

nordec · 05. 03. 2010 13:14

Mohl by, prosím, někdo poradit s tímto příkladem:
Dokažte, že $\alpha(G)>=\frac{n}{\Delta(G)+1}$ .

Vím, že $\alpha(G)$ je velikost největší nezávislé množiny grafu G, ale co je $\Delta(G)$ to netuším.

Za jakékoli rady děkuji.

Stýv · 05. 03. 2010 15:29

tipoval bych nejvyšší stupeň v grafu, ale ruku do ohně bych za to nedal

petrkovar · 05. 03. 2010 21:09

↑ nordec:Když z grafu vyhodíme libovolný vrchol x a všechny jeho sousedy, kolikrát vrcholů odebereme?
Když tento odebraný vrchol x započítáme do nezávislé množiny vrcholů, bude sousední (samozřejmě po odebrání i sousedů), s některým zbývajícícm vrcholm v grafu?
Kolikrát to můžeme udělat?

nordec · 06. 03. 2010 14:50

↑ Stýv:
Někde na internetu jsem zase našel, že delta je minimální stupeň grafu. Tak pořád nevím, jak to je.

↑ petrkovar:
ot.1: Odebereme tolik vrcholů, kolik je stupeň x a ještě vrchol x. (Předpokládám, že v otázce bylo myšleno kolik, ne kolikrát.)

ot.2: Vrchol x nebude sousední s žádným vrcholem grafu, protože sousední jsme odebrali.

ot.3: Budeme odebírat vrcholy, dokud v grafu budou. Vrcholů je n a na jedno odebrání spotřebujeme stupeň odebíraného vrcholu + 1 vrcholů. Můžeme to tedy udělat tolikrát, kolik je počet odebrání jednoho vrcholu (i se sousedy) a to je zároveň velikost výsledné nezávislé množiny (,která nebude největší). Ale když každý vrchol může mít jiný stupeň, tak to asi nepůjde spočítat jako podíl n a počtu vrcholů spotřebovaných na jedno odebrání, že?

petrkovar · 06. 03. 2010 21:04

↑ nordec:I Řecká abeceda má malá a velká písmena. $\delta(G)$ je nejmenší stupeň v grafu a $\Delta(G)$ je největší stupeň v grafu. Je-li $\delta(G)=\Delta(G)$ , tak $G$ má všechny vrcholy stejného stupně.

k ot1. Ano, Původně jsem měl všechno v jedné otázce, pak jsem to rozepsal a toto slovo jsem zapomněl opravit. Naštěstí čtenáře to nezmátlo ;-)

A hlavně k ot3.
Samozřejmě pokud jsou vrcholu různých stupňů, tak nedostaneme rovnost. Ale o rovnost podle zadání nejde, že? Jde o dolní odhad. A my víme, že stupeň každého vrcholu je nejvýše $\Delta(G)$ ...

nordec · 06. 03. 2010 22:01

Zkoušel jsem nakreslit nějaké grafy a myslím, že pro $\delta(G)$ ta nerovnice ani neplatí, tak už mám ve značení jasno :)

K ot.3: To znamená, že najednou odebereme max. $\Delta(G)+1$ vrcholů. A $\frac{n}{\Delta(G)+1}$ je menší nebo rovno dokonce i nejmenší nezávislé množině grafu?

petrkovar

↑ nordec:Skoro ;-)
Nejmenší nezávislá množina vrcholů není smysluplný pojem. Byla by to prázdná množina? Nebo jednoprvková množina s libovolným vrcholem?
při poisu fomálního důkazu doporučuji postupovat o"od známého k neznámému".
Vzít nějakou největší nezávislou množinu vrcholů, přidat jejich sousedy a výsledek porovnat s $n$ . Vyjádřit $\alpha(G)$ pak nebude problém.

nordec · 07. 03. 2010 22:17

Takže něco jako:
Víme-li, že každý vrchol z největší nezávislé množiny má maximálně $\Delta(G)$ sousedů, potom graf G má nejvíce $\alpha(G).\Delta(G)+\alpha(G)$ vrcholů. Počet vrcholů označíme n a po úpravě nerovnice $\alpha(G).\Delta(G)+\alpha(G)>=n$ dostaneme $\alpha(G)>=\frac{n}{\Delta(G)+1}$ . Nerovnice bude platit i pro grafy s menším počtem vrcholů, protože zmenšením čitatele (n) a zachováním jmenovatele zmenšíme celý zlomek a tím snížíme dolní odhad největší nezávislé množiny, což nám ho nepokazí.

dalo by se považovat za důkaz?

petrkovar

nordec napsal(a):
Nerovnice bude platit i pro grafy s menším počtem vrcholů, protože zmenšením čitatele (n) a zachováním jmenovatele zmenšíme celý zlomek a tím snížíme dolní odhad největší nezávislé množiny, což nám ho nepokazí.

Tato část je vlastně navíc. Vždyť už máme nerovnost. Stačí je jedno větou řící, co ta nerovnost zachycuje.

nordec · 10. 03. 2010 17:30

Aha.
Nejdřív jsem nevěděl, co ten zlomek vlastně znamená a teď už vím.
Moc jsi mi pomohl, díky.

Matematické Fórum

#1 05. 03. 2010 13:14

Největší nezávislá množina v grafu

#2 05. 03. 2010 15:29

Re: Největší nezávislá množina v grafu

#3 05. 03. 2010 21:09

Re: Největší nezávislá množina v grafu

#4 06. 03. 2010 14:50

Re: Největší nezávislá množina v grafu

#5 06. 03. 2010 21:04

Re: Největší nezávislá množina v grafu

#6 06. 03. 2010 22:01

Re: Největší nezávislá množina v grafu

#7 07. 03. 2010 21:07 — Editoval petrkovar (07. 03. 2010 21:08)

Re: Největší nezávislá množina v grafu

#8 07. 03. 2010 22:17

Re: Největší nezávislá množina v grafu

#9 09. 03. 2010 21:08 — Editoval petrkovar (10. 03. 2010 20:31)

Re: Největší nezávislá množina v grafu

nordec napsal(a):

#10 10. 03. 2010 17:30

Re: Největší nezávislá množina v grafu

Zápatí