Witam!
Nie mogę znaleźć odpowiedzi na te zadania
1) Ile krawędzi w grafie \(\displaystyle{ K_{50,51,150}}\) ma jego drzewo rozpinajace?
2) Ile krawędzi ma graf \(\displaystyle{ K_{50,51,150}}\)>
3) Pełny graf \(\displaystyle{ K_{109,81,27}}\) jest? Uzasadnij.
a)grafem Eulerowskim,
b)jest trójkolorowalny,
c)jest dwudzielny,
d)jest grafem Hamiltonowskim,
Ile krawedzi w grafie K50,51,150 ma jego drzewo rozpinajace
-
legendarny ziom
- Użytkownik
- Posty: 17
- Rejestracja: 3 cze 2012, o 23:05
- Płeć: Mężczyzna
- Lokalizacja: nibylandia
Ile krawedzi w grafie K50,51,150 ma jego drzewo rozpinajace
2) Z tego co pamietam K50 oznacza graf pelny gdzie kazdą pare wierzcholkow laczy krawiedz.
Zatem, na ile sposobow mozemy wybrac pare wierzcholkow z grafu 50cio wierzcholkowego?
Z tego wynika ze (dwumian newtona) \(\displaystyle{ {50 \choose 2}}\)
Zatem, na ile sposobow mozemy wybrac pare wierzcholkow z grafu 50cio wierzcholkowego?
Z tego wynika ze (dwumian newtona) \(\displaystyle{ {50 \choose 2}}\)
-
TrzyRazyCztery
- Użytkownik
- Posty: 101
- Rejestracja: 24 maja 2014, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Wro
- Podziękował: 27 razy
- Pomógł: 1 raz
Ile krawedzi w grafie K50,51,150 ma jego drzewo rozpinajace
piczer08 Czy mógłbyś mnie upewnić że chodzi o graf \(\displaystyle{ K_{50,51,150}}\) a nie o 3 różne grafy \(\displaystyle{ K_{50}, K_{51}}\)\(\displaystyle{ K_{150}}\)?
Jesli tak: (od razu mówię, sam sie ucze aktualnie grafów, wiec traktuj moje wypowiedzi z dystansem, może to ewentualnie potwierdzić ktoś mądrzejszy ode mnie)
(1) Wydaje mi się że skoro jest to graf trójdzielny pełny, to jest spójny. A skoro jest spójny i posiada 251 wierzchołków to drzewo musi mieć 250 krawędzi
Co do (2) ile krawędzi ma graf \(\displaystyle{ K_{50,51,150}}\) To wydaje mi się że każdy pełny graf \(\displaystyle{ K_{r,s,t}}\) ma \(\displaystyle{ \frac{\left( r \cdot s\right) + \left( r \cdot t\right) + \left( s\cdot t\right)}{2}}\) Krawędzi, tak biorąc na logikę skoro w grafie trójdzielnym każdy ze zbiorów wierzchołków nie zawiera krawędzi miedzy swoimi wierzchołkami, a od każdego z wierzchołków istnieje krawędz do każdego z wierzchołków pozostałych dwóch zbiorów (bo jest to graf pełny)
(3)
\(\displaystyle{ a)}\) Eulerowski, Z Tw Eulera graf jest grafem eulerowskim wtedy i tylko wtedy gdy stopień każdego wierzchołka jest liczbą parzystą. W tym przypadku mamy \(\displaystyle{ K_{109,81,27}}\) Wiec widać (chyba ) że W tym grafie mamy \(\displaystyle{ 27}\) wierzchołków stopnia \(\displaystyle{ 190}\), \(\displaystyle{ 81}\) wierzchołków stopnia \(\displaystyle{ 136}\) i \(\displaystyle{ 109}\) wierzchołków stopnia \(\displaystyle{ 108}\). Wiec wszystkie wierzchołki są parzystego stopnia wiec graf jest eulerowski.
\(\displaystyle{ b)}\) Jest trójkolorowalny bo wystarczy pokolorować wierzchołki każdego ze zbiorów na inny kolor i wiemy że pomiedzy wierzchołkami danego koloru nie ma krawędzi wiec każdy wierzchołek sąsiaduje tylko z wierzchołkami innego koloru.
\(\displaystyle{ c)}\) Nie wiem jak to ładnie pokazać, ale weź 3 dowolne wierzchołki, po jednym z każdej grupy wierzchołków tego grafu trójdzielnego. nazwijmy je np \(\displaystyle{ v,u,w}\). \(\displaystyle{ v}\) posiada krawędz z \(\displaystyle{ u}\) wiec muszą leżeć w 2 oddzielnych zbiorach. wierzchołek \(\displaystyle{ w}\) musieli byśmy umieścić w którymś z tych zbiorów, nie możemy go umieścić ani z \(\displaystyle{ u}\) ani z \(\displaystyle{ v}\) ponieważ posiada z nimi krawędzie. Czyli nie mamy gdzie umieścić wierzchołka \(\displaystyle{ w}\) wiec graf nie może być dwudzielny.
Jesli tak: (od razu mówię, sam sie ucze aktualnie grafów, wiec traktuj moje wypowiedzi z dystansem, może to ewentualnie potwierdzić ktoś mądrzejszy ode mnie)
(1) Wydaje mi się że skoro jest to graf trójdzielny pełny, to jest spójny. A skoro jest spójny i posiada 251 wierzchołków to drzewo musi mieć 250 krawędzi
Co do (2) ile krawędzi ma graf \(\displaystyle{ K_{50,51,150}}\) To wydaje mi się że każdy pełny graf \(\displaystyle{ K_{r,s,t}}\) ma \(\displaystyle{ \frac{\left( r \cdot s\right) + \left( r \cdot t\right) + \left( s\cdot t\right)}{2}}\) Krawędzi, tak biorąc na logikę skoro w grafie trójdzielnym każdy ze zbiorów wierzchołków nie zawiera krawędzi miedzy swoimi wierzchołkami, a od każdego z wierzchołków istnieje krawędz do każdego z wierzchołków pozostałych dwóch zbiorów (bo jest to graf pełny)
(3)
\(\displaystyle{ a)}\) Eulerowski, Z Tw Eulera graf jest grafem eulerowskim wtedy i tylko wtedy gdy stopień każdego wierzchołka jest liczbą parzystą. W tym przypadku mamy \(\displaystyle{ K_{109,81,27}}\) Wiec widać (chyba ) że W tym grafie mamy \(\displaystyle{ 27}\) wierzchołków stopnia \(\displaystyle{ 190}\), \(\displaystyle{ 81}\) wierzchołków stopnia \(\displaystyle{ 136}\) i \(\displaystyle{ 109}\) wierzchołków stopnia \(\displaystyle{ 108}\). Wiec wszystkie wierzchołki są parzystego stopnia wiec graf jest eulerowski.
\(\displaystyle{ b)}\) Jest trójkolorowalny bo wystarczy pokolorować wierzchołki każdego ze zbiorów na inny kolor i wiemy że pomiedzy wierzchołkami danego koloru nie ma krawędzi wiec każdy wierzchołek sąsiaduje tylko z wierzchołkami innego koloru.
\(\displaystyle{ c)}\) Nie wiem jak to ładnie pokazać, ale weź 3 dowolne wierzchołki, po jednym z każdej grupy wierzchołków tego grafu trójdzielnego. nazwijmy je np \(\displaystyle{ v,u,w}\). \(\displaystyle{ v}\) posiada krawędz z \(\displaystyle{ u}\) wiec muszą leżeć w 2 oddzielnych zbiorach. wierzchołek \(\displaystyle{ w}\) musieli byśmy umieścić w którymś z tych zbiorów, nie możemy go umieścić ani z \(\displaystyle{ u}\) ani z \(\displaystyle{ v}\) ponieważ posiada z nimi krawędzie. Czyli nie mamy gdzie umieścić wierzchołka \(\displaystyle{ w}\) wiec graf nie może być dwudzielny.
Ile krawedzi w grafie K50,51,150 ma jego drzewo rozpinajace
Tak chodzi o jeden graf. Dużo mi rozjaśniłeś bo ciężko coś znaleźć ogólnie na temat grafów. Dzięki!