szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 maja 2016, o 14:20 
Użytkownik

Posty: 811
Niech X=\{1,...,9\}. Wierzchołkami grafu G=(V,E) są wszystkie 3-elementowe podzbioru zbioru X, a dwa wierzchołki łączymy krawędzią, gdy |A \cap B|=1.

Czy ten graf jest dwudzielny?

Wydaje mi się, że nie jest, bo nie da się podzielić zbioru wierzchołków na dwa tak, aby wierzchołki w tym samym zbiorze nie łączyły się ze sobą.
Nie wiem jednak jak to uzasadnić, graf dwudzielny to taki, który nie ma cyklów nieparzystej długości, może jakoś w tę stronę?
Spróbuję to jakoś uzasadnić słowami :
Dla uproszczenia, sprawdzę dla tych wierzchołków które mają ze soba wspólną tylko jedynkę, resztę pominę.
Jeżeli w pierwszym zbiorze chcielibyśmy np. zawrzeć wierzchołki zawierające elementy \{1,2,x\}, gdzie x\in \{3,4..,9\}, to te wierzchołki nie będą się ze sobą łączyć (nie możemy do pierwszego zbioru już nic włożyć, bo wtedy będziemy musieli połączyć wierzchołki z tymi o których wcześniej wspomniałem), ale wtedy w drugim zbiorze musimy uwzględnić wierzchołki \{1,y,x\}, gdzie x,y\in \{3,4,5,...,9\} \wedge x\neq y, a wtedy w drugim zbiorze znajdzie się na pewno \{1,3,4\} i \{1,5,6\} a te wierzchołki trzeba ze sobą połączyć.
To tylko przykład dla tych wierzchołków, które mają ze sobą wspólną jedynkę, wiadomo, że może być jeszcze wspólna dwójka i tak dalej aż do dziewiątki, ale to psuje się już dla samej jedynki, więc dalej tymbardziej się zepsuje.

Czy takie uzasadnienie byłoby w porządku?
Góra
Mężczyzna Offline
PostNapisane: 29 maja 2016, o 18:40 
Użytkownik

Posty: 1390
Lokalizacja: Poznań
(1,2,3), (3,4,5), (1,5,6) - cykl nieparzysty.. to wystarczy?
Góra
Mężczyzna Offline
PostNapisane: 29 maja 2016, o 20:57 
Użytkownik

Posty: 811
Ah, dzięki wielkie, nie sądziłem, że wskazanie cyklu nieparzystego będzie tak proste, najwidoczniej nie rozumiałem do końca tego pojęcia.
Góra
Mężczyzna Offline
PostNapisane: 31 maja 2016, o 13:16 
Użytkownik

Posty: 4
Lokalizacja: Kraków
Skorzystam i podepnę się pod temat. Czyli z tego co rozumiem, jeśli mam narysować graf pełny, planarny, dwudzielny to wystarczy np. P2?
Góra
Mężczyzna Offline
PostNapisane: 31 maja 2016, o 17:49 
Użytkownik

Posty: 1390
Lokalizacja: Poznań
Jeśli P2 to graf na dwóch wierzchołkach z krawędzią między nimi to tak :D
Góra
Kobieta Offline
PostNapisane: 31 maja 2016, o 21:21 
Użytkownik
Avatar użytkownika

Posty: 14
Wracając jeszcze do powyższego grafu - w jaki sposób obliczyć stopień wierzchołka? Rozważając np. dla podzbioru \left\{ 1,2,3\right\}.
Próbuję zrobić to kombinatorycznie: ilość wszystkich podzbiorów X będzie równa C_9^3, chcę odjąć od tego wszystkie podzbiory, które nie będą miały wspólnych elementów z \left\{ 1,2,3\right\} i będzie ich C_6^3. Następnie odejmuję te, które będą miały wspólne dwa elementy, czyli 3*6. Ostatecznie dostaję deg(v)=45. Czy to by było dobrze?
I jak uzasadnić, że każdy wierzchołek ma ten sam stopień?
Góra
Mężczyzna Offline
PostNapisane: 1 cze 2016, o 16:42 
Użytkownik

Posty: 1390
Lokalizacja: Poznań
Stopień się zgadza chociaż ja doszedłem do tego nieco inaczej.. W moim przypadku od razu zauważymy, że każdy wierzchołek ma ten sam stopień:

Wybieram dowolny wierzchołek, niech to będzie np v=\left\{ x,y,z\right\}. Znajdźmy wszystkie wierzchołki, z którymi mój wierzchołek v jest połączony krawędzią.. Ano te wierzchołki to np te, które posiadają element x i nie posiadają elementów y i z.. Pozostałe dwa elementy mogę wybrać na {6 \choose 2}=15 sposobów.. Mam więc 15 3-elementowych podzbiorów X w których mam x a nie mam y i z.. Identycznie jest z pozostałymi dwoma przypadkami kiedy obieram za element wspólny y, a następnie z.. Z dowolności wyboru wierzchołka wnioskuję, że każdy wierzchołek w grafie musi mieć ten sam stopień.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 Dany jest zbiór A={a,b,c,d}  Nanu  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl