szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 lis 2015, o 20:40 
Użytkownik

Posty: 83
Lokalizacja: Brak
Cześć, mam problem z udowodnieniem takiego oto faktu:

Cl_k(G) nie zależy od kolejności dodawania krawędzi.

Cl_k(G) czyli k-te domknięcie B&Ch grafu G to graf otrzymany przez kolejne dodawanie krawędzi między wierzchołkami x i y dla, których suma stopni jest co najmniej k.

Macie pomysły?

-- 4 lis 2015, o 00:59 --

Pomysł: Załóżmy, że w G istnieje k_1 takich par wierzchołków, że suma ich stopni jest co najmniej n, gdzie n to rząd grafu.

Załóżmy, ze pierwsze domknięcie konstruujemy łącząc k_1 par krawędzią. Powstanie wtedy zbiór k_2 nowych par spełniających założenia o sumie stopni wierzchołków większej niż rząd grafu. Łączymy te pary i znowu powstanie kolejny taki zbiór. Kontynuujemy aż do momentu gdy już nie będzie żadnej pary. Ten moment nastąpi ponieważ zakładamy, że zbiór wierzchołków jest skończony. (Jak ktoś wie jak to zrobić dla nieskończonego to chętnie się wczytam.)

Teraz chce pokazać, że każda inna kolejność wyboru kolejnej pary dla której "wstawię" krawędź prowadzi do tego samego domknięcia co z akapitu wyżej. I tak w istocie jest, w każdej konstrukcji domknięcia musimy wstawić krawędzie w pary z k_1 ponieważ dla nich warunek nigdy nie przestanie być spełniony. Nawet jeżeli najpierw dodamy krawędzie tylko do kilku par z k_1
a następnie do par z innych zbiorów np. k_2 to tak czy inaczej w końcu musimy połączyć pary ze zbioru pierwszego. Nie ważne jakie weźmiemy pary i tak nie będziemy w stanie wygenerować innej pary spełniającej założenia i nie należącej do zbiorów k_i.


Prosiłbym o weryfikacje, mam wątpliwości czy jest poprawny.

-- 5 lis 2015, o 00:59 --

Można zamknąć. Osobiście uznaję problem za rozwiązany. Dowód powyżej.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 operator domknięcia  bartek87  0
 Teoria grafów, dowód twierdzenia Bondy'ego-Chvatala  kgrafy  0
 znależć Generatory i domkniecia  witu12  4
 domkniecie bondego-Chvatala  snd0cff  0
 wnetrza i domkniecia w róznych metrykach  xxmonikaxx  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl