Graf spójny
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Graf nazywamy spójnym, jeśli dla każdej pary wierzchołków istnieje marszruta je łącząca.
Graf nie posiadający powyższej własności to graf niespójny.
Warunkiem koniecznym na to, by graf skierowany był spójny, jest spójność jego grafu podstawowego (tego samego grafu bez kierunków na krawędziach).
Maksymalny w sensie inkluzji spójny podgraf grafu nazywamy spójną składową. Ilość spójnych składowych grafu G oznacza się przez 
.
Inaczej spójną składową grafu G jest jego spójny podgraf nie zawarty w większym podgrafie spójnym grafu G.
Nieformalnie spójna składowa grafu jest to taki podgraf, który można 'wydzielić' z całego grafu bez usuwania krawędzi. Graf spójny ma jedną spójna składową. Dla przykładu, w lesie spójnymi składowymi są drzewa.Spójna składowa to fragment grafu, który nie jest połączony z innym fragmentem.
Oczywiście 
oznacza, że graf G jest spójny,
oznacza, że G składa się z | G(V) | izolowanych wierzchołków.
Wierzchołek v nazywa się rozspajającym graf G (albo przegubem w grafie G), jeżeli usunięcie v z G (wraz z przyległymi do niego krawędziami) powoduje zwiększenie (czyli jeśli po usunięciu v wraz z przyległymi do niego krawędziami, graf G ma więcej składowych niż wcześniej).
[edytuj] Przykład
Graf ten jest spójny, więc zgodnie z definicją ma jedną spójną składową.
Po usunięciu krawędzi 2-3 i 4-5 graf ten nie jest już spójny, składa się wtedy z dwóch oddzielnych zbiorów wierzchołków:
Każdy z tych zbiorów jest spójną składową grafu, a więc łącznie cały graf posiada dwie spójne składowe - 
.
[edytuj] Zobacz też:
| O światowym kryzysie w Białym Domu |
 Ministrowie finansów najbogatszych siedmiu krajów świata na spotkaniu w Białym Domu szukali recepty na wyjście z ogarniającego świat kryzysu. Mamy plan -ogłosili po spotkaniu prezydentem Georgem W.Bushem. Tymczasem Rosja dopomina się, aby i ją włączyć w rozwiązywanie gospodarczych problemów.
|
| Stan wojenny w USA, wyborów nie będzie? |
 4 listopada wyborów w USA nie będzie. Administracja prezydenta George'a W. Busha, pod pretekstem kryzysu finansowego, wprowadzi stan wojenny i przesunie głosowanie na później. Spokojnie - to tylko plotka, ale żywiołowa dyskusja na ten temat przetacza się przez blogi i internetowe fora - informuje portal "Rzeczpospolitej".
|
| Rośnie bilans ofiar trzęsienia ziemi |
 Do dwunastu wzrosła liczba ofiar trzęsienia ziemi, do którego doszło w sobotę na Północnym Kaukazie - poinformowało rosyjskie Ministerstwo ds. Sytuacji Nadzwyczajnych. Epicentrum znajdowało się koło małej czeczeńskiej wsi Wiedieno.
|
| Bush: kryzys wymaga globalnej reakcji |
 - Wszyscy zdajemy sobie sprawę, że jest to poważny kryzys globalny i właśnie dlatego wymaga on globalnej reakcji - powiedział George W. Bush po sobotnim spotkaniu z ministrami finansów i szefami banków centralnych państw G7.
|
| Korea (oficjalnie) nie wspiera już terrorystów |
 Amerykański Departament Stanu ogłosił że skreśli Koreę Północną z listy państw finansujących terroryzm, o czym wcześniej wspominały anonimowe źródła dyplomatyczne. Stało się to po tym, gdy Phenianu wyraził zgodę na inspekcję instalacji nuklearnych.
|