MathTextOntology-pasek

Rozważmy abstrakcyjny graf G. Nieformalnie abstrakcyjny graf matematyczny to obiekt złożony ze zbioru wierzchołków oraz zbioru krawędzi łączących wierzchołki. Wierzchołki połączone wspólną krawędzią nazwiemy sąsiadującymi.

W zastosowaniach zwykle wierzchołki posiadają jakieś konkretne cechy ( i zwykle mają etykietki ), zaś fakt łączenia wierzchołków krawędzią, zwykle ma jakąś interpretację. W ramach rozlicznych interpretacji, możemy mówić o posiadaniu przez wierzchołek określonej własności X. X będziemy tu traktowali jako predykat o dziedzinie w zbiorze wierzchołków, a wartościach w zbiorze {T,F} reprezentującym prawdę i fałsz. Tym samym jeśli wybierzemy pewien wierzchołek v grafu G, to możemy zapytać jaka jest wartość X(v), oraz powiemy że v ma własność X jeśli X(v) = T lub krócej będziemy pisać że X(v).

Przy takiej dosyć prostej terminologii, możemy sformułować w miarę oczywistą zasadę indukcji na grafie.

    Zasada indukcji na grafie.

Dany jest graf nieskierowany G, z jedna składową spójną. Załóżmy że zachodzą następujące własności:

  1. dla każdego wierzchołka v grafu G z tego że X(v) wynika, że X zachodzi dla każdego wierzchołka sąsiadującego z v.
  2. dla pewnego wierzchołka a zachodzi własność X

    Teza: X jest prawdziwe dla wszystkich wierzchołków grafu G.

Dowód ( niewprost):

Załóżmy że spełnione jest założenie (2), to znaczy istnieje wierzchołek a dla którego zachodzi X, oraz spełniona jest zasada (1), że z faktu że X zachodzi dla pewnego wierzchołka wynika ze zachodzi dla wszystkich połączonych z nim wierzchołków.  Mimo to twierdzimy że twierdzenie nie jest prawdziwe, to znaczy że  istnieje pewien wierzchołek d dla którego X nie jest prawdziwe.

Załóżmy że istnieje pewien wierzchołek s sąsiadujący z d dla którego X(s). Wówczas z (1) wynika że d ma cechę X podczas gdy w poprzednik kroku założyliśmy że d nie posiada cechy X. Sprzeczność. Wynika z tego że żaden wierzchołek sąsiadujący z d nie może posiadać cechy X.

Wierzchołki sąsiadujące z nimi także itp, itd.

Oznaczmy przez U zbiór wierzchołków które nie posiadają cechy X. Zbiór U jest niepusty bo zawiera co najmniej wierzchołek d, a także  wierzchołki sąsiadujące z d, wierzchołki sąsiadujące z tymi wierzchołkami itd. Innymi słowy zbiór U to składowa spójna grafu zawierająca d.

Jednak z założenia graf jest grafem spójnym, posiada więc jedna składową spójna.

W takim razie A należy do U.

Ale dla A zachodzi X.
Sprzeczność.
Co prawda zasada wydaje się w miarę oczywista, ale nie znalazłem jej w google ;-)

Po drugie, oczywista to ona pewnie jest dla grafów skończonych, ale z dowodu wydaje się wynikać, ze dla nieskończonych także, co więcej, prosty dowód nie narzuca jakichś ograniczeń na moce zbiorów wierzchołków…