Grafy :: počty hran

[Houp]

[rezna]

nj my bad - uz mi to nemysli v tuhle hodinu ...

[sulthan]

Je dneska uz trosku pozde na to, abych prisel s nejakou vybornou myslenkou, ale uvazuju zhruba takhle. Vsech tech 2500 vrcholu seradim do kruhu.
Pro kazdy z nich vygeneruju 1 hranu tim, ze ho pripojim k vrcholu, co za nim nasleduje.
Hranu c. 2 vygeneruju pripojenim kazdeho vrcholu k vrcholu co je o 2 pozice dal.
atd. atd. az do kroku 400.

Pak by mel mit kazdy vrchol stupen 800 protoze 400 vrcholu se k nemu pripojilo a ke 400 se pripojil sam a ony mnoziny jsou disjunktni.

Delam nekde chybu?

[VODA]

Jo jo, na to už jsem také přišel...připoměla mi to kamarádka z ročníku...
_________________
Opravdovost se pojí s trýzní...

[Al]

Já nikdy nestudoval teorii grafů (přiznávám se, to jsme ve škole prostě neměli), takže jen jednoduchým selským rozumem (a vyřešilo by to i dítě ze základky, jestli je má úvaha správná ):

Je-li daný počet uzlů sudý, tak vždy lze vytvořit graf dle zadání až pro stupeň N-1. Je-li daný počet uzlů lichý, tak to naopak nejde nikdy. To je vše.

(Omlouvám se předem, jestli to není dobře. Je to až podezřele triviální řešení, že jo.)

Edit: Pro lichý počet uzlů to jde pro případ nula hran. To já jen pro případné grafovoteoretické puntičkáře, ty tyhle nesmysly zajímají vždycky nejvíc ze všeho.

[VODA]

Já bych chtěl doplnit, že u lichých to také lze, Ale co jsem tak zkoušel, tak jen se sudými stupni...třeba 5 uzlů stupně 4...

_________________
Opravdovost se pojí s trýzní...

[sulthan]

Urcite nepujde lichy pocet uzlu spolu s lichym stupnem (soucet vsech stupnu by nebyl sudy).
Lichy stupen a sudy stupen uzlu muze jit (priklad - kazdy sudy uplny graf).
Sudy stupen a lichy pocet uzlu nebude delat moc rozdil od sudeho poctu uzlu (jestli mame 2500 nebo 2501 vrcholu vyjde na stejno, kdyz chceme stupen 800).

IMHO to obecne spis pujde nez nepujde.

[Al]

Ráno moudřejší večera!!

Ještě než jsem se stihl nasnídat, napadlo mě, že ta původní má "lichá" teorie má chybu - přesně tu, o které psal sulthan. Řekl bych, že ta lichost je správná myšlenka, ale jde jen o to, aby
1. počet hran byl menší než počet uzlů
2. počet hran NEBO počet uzlů byl sudý
(Spojka nebo dovoluje, aby platilo obojí. Nebo prostě aspoň jedno z toho. )

Jsem přesvědčen, že ten případ lichosti je opravdu jediným důvodem, proč by to nemělo jít. Když si rozepíšete větu, kterou tu psal kldosi (OnraSej?), tak to taky vychází na výše uvedené.
_________________
Děcka, mám doktorát z informatiky a aplikované matematiky, tak se se mnou laskavě nehádejte.

(Každej tu má nějakej zaručeně tvrďáckej podpis, tak já teď taky. )

[VODA]

Ano, tak to je. Tím se mi to vše hodně zjednodušuje. To jsem rád.
_________________
Opravdovost se pojí s trýzní...

[Marek]

Al> Takže ty máš doktorát z informatiky a apl. matematiky a neměl jsi teorii grafů? Nezpochybňuje to trochu kvalitu tvého vzdělání?
_________________
AMD Open Source Graphics Driver Developer

[igor]

Už to tady je asi vyřešeno, ale nebyla tu naznačena konstrukce takových grafů (resp. byla ale ne úplně pro všechny případy).

stupně - S, vrcholy - N, S<N

Pro sudé stupně a libovolný počet vrcholů jde použít tu sulthanovu metodu - bude to fungovat vždy, problém by nastal, pokud by to napojování S/2 vrcholů přesáhlo půlku "kružnice", což se nestane.

Pro liché stupně to jde udělat podobně - uděláme graf pro S-1 stupňů, pak propojíme hranou každé 2 "středově symetrické" vrcholy - ty ještě určitě nejsou propojené ((S-1)/2 tam "nedosáhne") a pro sudá N taková symetrie existuje.

Pro lichá N a lichá S to už tu bylo rozebráno, mě napadla taky taková myšlenka: počet hran v grafu musí být (S*N)/2, což pro lichá S,N není celé číslo.