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

Posty: 2
Lokalizacja: Kraków
Witam serdecznie, mam problem z zadaniem z matematyki dyskretnej, ciężko sobie wyobrazić jak ten graf wygląda, wydawało mi się że będzie on "symetryczny" (stopnie wierzchołków będą takie same), ale coś mi nie wychodzi, jeśli ktoś byłby w stanie mi pomóc będę bardzo wdzięczny :)

Niech X = {1, 2, . . . , 9}. Wierzchołkami grafu G = (V, E) są wszystkie 3−elementowe podzbiory zbioru X, a dwa wierzchołki A, B łączymy krawędzią wtedy i tylko wtedy, gdy \left| A \cap  B\right| = 1 .
(1) Znajdź \left|E\right|,
(2) Czy G ma cykl Hamiltona?
(3) Czy G ma obwód Eulera?
(4) Czy G jest grafem dwudzielnym?

Wyszło mi że \left| V\right|= {9 \choose 3} = 84,   a \left| E\right| =  \frac{ {9 \choose 1}  {8 \choose 2}  {6 \choose 2}  }{2} = 1890

Z góry dzięki za pomoc :)!
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2015, o 19:32 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
w |E| nie powinno być tego {9 \choose 1}, jedynkę wybierasz na 1 sposób, wszystkich wierzchołków z jedynką jest {8 \choose 2} i dla każdego z nich jest {6 \choose 2} takich, gdzie jest jedynka i dwie inne liczby

czyli |E| = 210
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2015, o 20:19 
Użytkownik

Posty: 2
Lokalizacja: Kraków
Ale tu nie chodzi o takie podzbiory trzyelementowe które mają w sobie jedynkę, tylko takie które mają dokładnie jeden element wspólny (co z resztą się zgadza, 210 \cdot  9 = 1890)
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2015, o 20:36 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
a przepraszam, nie zwróciłem uwagi na to, że tam jest moc przekroju
w takim razie jest ok
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 cykle hamiltona - grafy dwudzielne-problem nadal aktualny  mateuss  0
 koło a graf Eulera  manduka  0
 Funkcja eulera w zadaniach  nowik1991  13
 Zbiory niezależne w grafie a zależność rekurencyjna  pietr  9
 Liczba dróg Eulera  karad  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl