szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 cze 2016, o 17:50 
Użytkownik

Posty: 8
Lokalizacja: Śląsk
Niech n>0, a m \le {n}\choose{2}. Wykazać, że nieizomorficznych grafów o n wierzchołkach i m krawędziach jest tyle samo, co nieizomorficznych grafów o n wierzchołkach i {n}\choose{2}-m krawędziach.
Góra
PostNapisane: 3 cze 2016, o 19:19 
Użytkownik
Niech \mathcal{G} będzie rodziną wszystkich grafów o n ustalonych wierzchołkach i m krawędziach oraz niech \mathcal{H} będzie rodziną wszystkich grafów, o tych samych n wierzchołkach i {n\choose 2} -m krawędziach. Niech \eta : \mathcal{G} \to \mathcal{H} będzie funkcją przyporządkowującą grafowi G jego graf dopełniający \eta (G) . Jest jasne, że G_1 jest izomorficzny z G_2 wtedy i tylko wtedy, gdy \eta (G_1 ) jest izomorficzny z \eta (G_2 ) skąd wynika teza zadania.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczb chromatyczna grafu, a zbiór niezależny  mqtqbenc  1
 Dowód na istnienie grafu Hamiltona.  karpiuch  7
 kolorowanie grafu - graf planarny 3-kolorowalny  Algorytmistrz  2
 Rozkład grafu pełnego na trójkąty  Szemek  0
 Własność grafu krawędziowego  mol_ksiazkowy  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl