Matematické Fórum

hrubon · 23. 04. 2013 13:09 — Editoval hrubon (23. 04. 2013 13:17)

Zdravím,
potřebuji spočítat počet způsobů rozmístění k hran do bipartitního grafu o partitách m, n (kde m, n jsou počty vrcholů v jednotlivých partitách). Takže vstup je m, n a k a já potřebuji ten počet způsobů. Vítaná by byla rekurentní forma dle k (možná jednodušší na odvození). Ale moc fajn bude i uzavřený tvar. Už si s tím lámu hlavu pár hodin, vítaná je každá rada. Díky moc!

Pozadí problému:
máme za úkol vypočítat počet bipartitních grafů na v vrcholech. Mám ideu, jak na příklad jít, ale ne a ne ji dotáhnout... Je v-1 způsobů jak zvolit dvě partity. Takže suma přes nějaké i od 1 do v-1 a v ní se mi bude symetricky měnit m := i a n := v - i. V téhle sumě ještě jedna suma od 1 do m*n a v ní mám problém

OiBobik · 23. 04. 2013 15:18

↑ hrubon:

Ahoj,

A to jako ty grafy pocitas "az na isomorfismus"? (To reaguju ja to "je v-1 zpusobu, jak urcit dve partity")

Nicmene, at uz tak ci onak, takovy pristup bude potreba nejak vylepsit - hrozi ti, ze nektere grafy budes pocitat vicekrat - treba prazdny graf (tj vrcholy bez hran) je bipartitni, ale partity si muzes zvolit vice zpusoby.

hrubon · 23. 04. 2013 17:24

↑ OiBobik:

To v zadání specifikováno není. Takže předpokládejme, že počítáme i navzájem izomorfní grafy. n-1 způsobů jsem napsal proto, že když si seřadím n vrcholů do řady vedle sebe, tak je přesně n-1 zpsobů, jak mezi ně vtěsnat "zarážku" a rozdělit je na dvě neprázdné skuipny. (Pokud by jedna ze skupin byla prázdná, nejednalo by se o bipartitní graf, pokud se nepletu - možná se pletu).

Prázdný graf přeci zrovna budu počítat jen jednou, ne? Prázdných grafů je tam přesně v-1, takže stačí, aby mi ta vnitřní suma vždycky vyhodila pro svůj první (nebo tedy nultý) člen číslo jedna. No a samozřejmě záleží na tom, co bude uvnitř té sumy - a na to se právě neúspěšně snažím přijít.

Na to už jsem také narazil, abych nepočítal něco dvakrát... A s tím mám právě problém. Pro jednu hranu je to m*n způsobů. Takže např pro graf m=3, n=2 je a1=6 no a a2 pak něco jako:
(mn-1)+(mn-2)+(mn-3)+(mn-4)+(mn-5)+(mn-6)
a3:
(mn-2)+2(mn-3)+3(mn-4)+4(mn-5)+(mn-6)
Ale opravdu nevím, jestli to je správně a kam se ta rekurze dere. Čekal jsem, že to z toho vyleze, ale ono se tomu nějak nechce... Ty výrazy výše jsem odvodil z horlivého kreslení grafů, kde jsem si zkoušel vždycky pár hran zafixovat a ostatní různě permutovat a dělat to nějak "systematicky", abych na nic nezapomněl, ale ani nic nezopakoval, což je opravdu dost neprofi přístup a člověk nemá moc jistotu, proto píšu sem. Díky!

OiBobik

↑ hrubon:

Ahoj,
Tak trochu jinak:
0) ocislujme vrcholy, na kterych se pohybujeme, cisly 1, ..., n.

1) kdyz mas zafixovane dve parttity A a B (tj $A\cup B= \{1 \dots n\}, A\cap B =\emptyset, |A|=k, |B|=n-k$ ), pak kazdy bipartitni graf s temito dvema partitami jednoznacne urcis vyctem jeho hran. Pricemz povolene hrany jsou prave vsechny hrany, ktee maji jeden vrchol v A a druhy v B. Tech je zrejme $k(n-k)$ a libovolna podmnzina techto hran urcuje prave jeden bip. Graf s partitami A a B. Je jich tedy $2^{k(n-k)}$ . Kdybys do toho chtel zapojit jeste ten fixni pocet hran, dejme tomu m, bude to zkratka prislusne komb. Cislo, tedy ${k(n-k) \choose m}$ .

No a ted ten hacek: takto jsme sice hezky spocitali pro fixni partity pocet bip. Grafu, ale nemuzeme to jen tak secist pres vsechny volby mnozin A a B. Pokud totiz napriklad G bude graf s jednou hranou {1,4},, tak bude bipartitni pro spoustu ruznych voleb partit. Takze bychom tentyz graf zapocitali napr pro volby

A={1}, B={2, ... n}
A={2}, B={1,3,4, ... n}
A={1,2}, B={3,4, ... n}

Apod. Takze to chce bud nejak chytre priradit jednotlivym zpusobum volby partit jen nektere z tech bip. Grafu (tak, aby to bylo disjunktni pro ruzne volby partit a zaroven nejak rozumne upocitatelne), anebo tu myslenku rozclenovat to podle partit opustit uplne a zkusit to nejak jinak. At uz tak ci onak, myslim, ze to povede na nejakou formu principu inkluze a exkluze.

Jo a pozn: kdyz ti nejde o pocet az na isomorfismus ale jen o pocet, tj zalezi t na jmenech vrcholu, pak je pocet partit vic, nez n-1 ... a sice $2^{n-1}-1$ .

hrubon · 23. 04. 2013 19:28

↑ OiBobik:
Díky moc, úžasný! zkusím to nějak dorazit. :D

Matematické Fórum

#1 23. 04. 2013 13:09 — Editoval hrubon (23. 04. 2013 13:17)

Počet způsobů spojení dvou partit grafu

#2 23. 04. 2013 15:18

Re: Počet způsobů spojení dvou partit grafu

#3 23. 04. 2013 17:24

Re: Počet způsobů spojení dvou partit grafu

#4 23. 04. 2013 18:24 — Editoval OiBobik (23. 04. 2013 19:01)

Re: Počet způsobů spojení dvou partit grafu

#5 23. 04. 2013 19:28

Re: Počet způsobů spojení dvou partit grafu

Zápatí