Cześć, mam problem z udowodnieniem takiego oto faktu:
\(\displaystyle{ Cl_k(G)}\) nie zależy od kolejności dodawania krawędzi.
\(\displaystyle{ 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 \(\displaystyle{ G}\) istnieje \(\displaystyle{ k_1}\) takich par wierzchołków, że suma ich stopni jest co najmniej \(\displaystyle{ n}\), gdzie \(\displaystyle{ n}\) to rząd grafu.
Załóżmy, ze pierwsze domknięcie konstruujemy łącząc \(\displaystyle{ k_1}\) par krawędzią. Powstanie wtedy zbiór \(\displaystyle{ 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 \(\displaystyle{ k_1}\) ponieważ dla nich warunek nigdy nie przestanie być spełniony. Nawet jeżeli najpierw dodamy krawędzie tylko do kilku par z \(\displaystyle{ k_1}\)
a następnie do par z innych zbiorów np. \(\displaystyle{ 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 \(\displaystyle{ 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.