Grafy :: počty hran

[VODA]

Zdravím,

dělám teď semestrálku do školy, ve které máme monstrózní graf (2500 uzlů) a mě by zajímalo, zda-li se dá nějak spočítat, jestli je možné udělat u každého N hran (bacha je to neorientovaný graf, takže A->B je totéž co B->A)
Máme totiž 2500 uzlů a každý má mít 800 hran k sousedům, ale když generuji ty hrany, tak několik posledních uzlů zkrátka 800 hran nemá...

Mám zato, že jsme se to učili v diskrétní matematice, ale jaksi to nemohu nikde najít...resp. jsem línej to hledat...

Díky za pomoc...
_________________
Opravdovost se pojí s trýzní...

[rezna]

a jak je generujes? jaka jsou pravidla?

neorientovany graf (pokud je uplny) ma z kazdeho uzlu (n-1) hran (spojuje se na vsech ostatnich (n-1) uzlu.

nebo mate pravidlo ze vsechny uzly musi mit prave 800 nalezejicich hran?

[rezna]

i tak - proste udelej na kazdem uzlu nahodnych 800 hran a musi to platit - a nebo mi chybi neco v zadani ...

[VODA]

Každý uzel musí mít právě 800 hran, uzlů je 2500 a mě zajímá, zda-li to je vůbec možné

Edit: Znovu poznamenávám, že je to neorientovaný graf...
_________________
Opravdovost se pojí s trýzní...

[rezna]

no pak ale teda specifikuj co znamena ze uzel ma 800 hran - protoze ja porad tvrdim ze takovy graf existuje - a ackoliv A->B == B->A porad uzel A muze mit 800 hran a uzel B taky

nejak chybi nejaka podminka, kdy se dana hrana na uzlu nepocita nebo jak to je

tzn. je-li hrana mezi uzly A a B plati ze je to +1 pro A a +1 pro B nebo jak?

pokud ano tak nejtrivialnejsi takovy graf je simply graf, kde kazdemu uzlu nagenerujes 800 uzlu (zcela nahodne treba) a slus

[frca]

Napadla mě jenom taková blbost: Vezmi dvojice uzlů a každou z nich propoj pomocí 800 hran. Je to jedna z mnoha možností, ale asi nejsnáze pochopitelná.
_________________
www.FRANTICWARE.com

[VODA]

To rezna: Jj, pokud je hrana mezi A a B (B a A), tak +1 k A a +1 k B
_________________
Opravdovost se pojí s trýzní...

[pcmaster]

[VODA]

Koukněte se na obrázek, tam mám 6 uzlů a každý musí mít 3 hrany...


Číslo udává počet hran, tak mi teda řekněte, kam mám spojit poslední dva uzle, aby všude bylo číslo 3...
_________________
Opravdovost se pojí s trýzní...

[rezna]

@pcmaster ja uz mozna vim kam miri - problem bude v tom ze pokud nahodne nageneruju kazdemu uzlu 800 hran, nutne tim nekterym uzlum omylem pridelam udelam vic nez 800

tak to bude chtit trochu premysleni

[OndraSej]

Na tohle je v diskretce veta, ktera rika, ze kdyz

1) vezmes skore grafu (== vektor, ve kterem mas pro kazdy uzel grafu pocet odchozich hran a cele to je serazene vzestupne podle poctu hran)
2) pokud mas nejaky vektor X podle (1), a vyrobis z nej vektor Y tak, ze odtrhnes nejvyssi hodnotu (tj. tu nejvic vpravo, necht je rovna N) a od N zbyvajicich nejvyssich hodnot v X odectes jednicky. Pak X je skore nejakeho grafu prave kdyz je Y skore nejakeho grafu.

S vyuzitim tehle vety - zacnes s vektorem, ve kterem mas 2500-krat 800 a postupne ubiras, Pokud narazis na stav, ve kterem nemuzes odebrat nejpravejsi hodnotu podle (2), treba protoze je vyssi nez pocet zbyvajicich prvku, tak graf s takovymi pocty hran na vrchol neexistuje.
_________________
http://trionteam.net

[Marek]

Ja bych si prostě napsal program, co mi to spočte tak, jak popisuje OndraSej. Jinak tohle je typická úloha, která se právě nejlíp řeší programem.
_________________
AMD Open Source Graphics Driver Developer

[igor]

Pokud to máš nějak obecněji počítat, tak samozřejmě funguje postup, který už tady psal Ondrasej. Pokud ale chceš pouze odpověď, zda takový graf s 800 hranami pro vrchol existuje a jak by mohl vypadat, tak jsem po chvilce přemýšlení přišel na to, že ano:

a) Uděláme úplný bipartitní graf K_800_800 - 2 skupiny po 800 vrcholech, každý vrchol ze skupiny A je propojen s každým vrcholem ze skupiny B, ale s žádným ze své skupiny. Takto jsme vyřešili 1600 vrcholů, zbývá 900.

b) Na těchto 900 vrcholech uděláme něco podobného jako v prvním případě - místo dvou uděláme 9 skupin po 100 vrcholech, každý vrchol ve skupině je propojen s každým vrcholem nepatřícím do jeho skupiny.

Pokud graf má být souvislý (to jsi nenapsal), tak vždy můžeš vzít 1 hranu A-B z podgrafu a), 1 hranu C-D z podgrafu b) a jejich vrcholy místo původních hran propojit "do kříže" (A-C, B-D).

[Fila]

Jeste muzes napsat brutforce algoritmus a vnoucatum vzkazat, at ti vysledek vytesaji na nahrobni kamen...

A Igorovo reseni je tak krasne jednoduche, az to cloveka nuti premyslet, kde je tam sakra bota .

[rezna]

K_{800,800} ma trabl ze kazdy vrchol ma jenom 799 hran ...