graf skonczony i cyklem- problem nadal aktualny

mateuss · Post autor: **mateuss** » 12 kwie 2008, o 14:21

Jak udowodnic, ze kazdy graf skonczony w którym każdy wierzchołek ma stopien wiekszy badź równy dwa zawiera cykl?

UNIX_admin · Post autor: **UNIX_admin** » 12 kwie 2008, o 15:00

a jaka moze byc maksymalnie suma stopni wierzch. w drzewie?

mateuss · Post autor: **mateuss** » 12 kwie 2008, o 15:26

a co z tym ma wspólnego drzewo?

kingataranek · Post autor: **kingataranek** » 10 gru 2008, o 21:41

Czy wie ktos moze jak to zrobic?

UNIX_admin · Post autor: **UNIX_admin** » 20 sty 2009, o 23:30

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.