Strona 1 z 1
graf skonczony i cyklem- problem nadal aktualny
: 12 kwie 2008, o 14:21
autor: mateuss
Jak udowodnic, ze kazdy graf skonczony w którym każdy wierzchołek ma stopien wiekszy badź równy dwa zawiera cykl?
graf skonczony i cyklem- problem nadal aktualny
: 12 kwie 2008, o 15:00
autor: UNIX_admin
a jaka moze byc maksymalnie suma stopni wierzch. w drzewie?
graf skonczony i cyklem- problem nadal aktualny
: 12 kwie 2008, o 15:26
autor: mateuss
a co z tym ma wspólnego drzewo?
graf skonczony i cyklem- problem nadal aktualny
: 10 gru 2008, o 21:41
autor: kingataranek
Czy wie ktos moze jak to zrobic?
graf skonczony i cyklem- problem nadal aktualny
: 20 sty 2009, o 23:30
autor: UNIX_admin
drzewo to taki graf bez cykli i bez wierzcholkow swobodnych. w drzewie wystepuja liscie, czyli wierzcholki o stopniu 1. rozpatrujemy tylko grafy skonczone (podane w zadaniu). wiadomo, ze dodanie nawet jednej krawedzi do drzewa powoduje powstanie cyklu. a przeciez nie ma innego sposobu na zwiekszenie stopnia wierzcholka niz dodanie krawedzi.
Formalny (i zwiezly) dowod mozna przeprowadzic wychodzac od oszacowania sumy wierzcholkow w drzewie.