szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 sty 2016, o 20:37 
Użytkownik

Posty: 2
Lokalizacja: krakow
Witam!

Nie mogę znaleźć odpowiedzi na te zadania

1) Ile krawędzi w grafie K_{50,51,150} ma jego drzewo rozpinajace?
2) Ile krawędzi ma graf K_{50,51,150}>
3) Pełny graf K_{109,81,27} jest? Uzasadnij.
a)grafem Eulerowskim,
b)jest trójkolorowalny,
c)jest dwudzielny,
d)jest grafem Hamiltonowskim,
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 28 sty 2016, o 00:04 
Użytkownik

Posty: 17
Lokalizacja: nibylandia
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) {50 \choose 2}
Góra
Mężczyzna Offline
PostNapisane: 28 sty 2016, o 02:11 
Użytkownik

Posty: 101
Lokalizacja: Wro
piczer08 Czy mógłbyś mnie upewnić że chodzi o graf K_{50,51,150} a nie o 3 różne grafy K_{50}, K_{51}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 K_{50,51,150} To wydaje mi się że każdy pełny graf K_{r,s,t} ma \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)
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 K_{109,81,27} Wiec widać (chyba :mrgreen: ) że W tym grafie mamy 27 wierzchołków stopnia 190, 81 wierzchołków stopnia 136 i 109 wierzchołków stopnia 108. Wiec wszystkie wierzchołki są parzystego stopnia wiec graf jest eulerowski.

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.

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 v,u,w. v posiada krawędz z u wiec muszą leżeć w 2 oddzielnych zbiorach. wierzchołek w musieli byśmy umieścić w którymś z tych zbiorów, nie możemy go umieścić ani z u ani z v ponieważ posiada z nimi krawędzie. Czyli nie mamy gdzie umieścić wierzchołka w wiec graf nie może być dwudzielny.
Góra
Mężczyzna Offline
PostNapisane: 28 sty 2016, o 13:17 
Użytkownik

Posty: 2
Lokalizacja: krakow
Tak chodzi o jeden graf. Dużo mi rozjaśniłeś bo ciężko coś znaleźć ogólnie na temat grafów. Dzięki!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 stopień w grafie a spójnośc  owen1011  7
 Cykl eulera w grafie i jego grafie krawędziowym.  krzysiel00  1
 Skojarzenia w grafie, minimalizacja sumy długości karawędzi.  e715489  0
 Cykl hamiltona w grafie o 6 wierzchołkach  gardner  4
 Podgraf dwudzielny w grafie  ucaps  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl