Przestrzenie krawędzi i wierzchołków

W matematycznej dyscyplinie teorii grafów przestrzeń krawędzi i przestrzeń wierzchołków grafu nieskierowanego to przestrzenie wektorowe zdefiniowane odpowiednio za pomocą zbiorów krawędzi i wierzchołków . Te przestrzenie wektorowe umożliwiają wykorzystanie technik algebry liniowej do badania grafów.

Definicja

Niech $_$ _ Przestrzeń wierzchołków ${$ $Displaystyle \$ przestrzenią wektorową nad skończonym polem dwóch elementów 2 1 wszystkich funkcji ${\ Displaystyle V \ rightarrow \ mathbb {Z} / 2 \ mathbb {Z}}$ . Każdy element z $przypisuje$ w naturalny sposób odpowiada podzbiorowi V , który 1 swoim wierzchołkom. $.$ każdy podzbiór V reprezentowany przez swoją charakterystyczną Przestrzeń krawędziowa jest przestrzenią wektorową dowolnie generowaną przez $Displaystyle \ mathbb {Z$ $Z}}$ zestaw krawędzi E . Wymiarem przestrzeni wierzchołków jest zatem liczba wierzchołków grafu, podczas gdy wymiarem przestrzeni krawędzi jest liczba krawędzi.

Definicje te można uściślić. Na przykład możemy opisać przestrzeń krawędziową w następujący sposób:

elementy są podzbiorami mi $Displaystyle E}$ \ , to znaczy jako zbiór jest ${\ displaystyle {\ mathcal {E}} (G)}$ mi
dodawanie wektorów definiuje się jako różnicę symetryczną : ${\ Displaystyle P + Q: = P \ trójkąt Q \ qquad P, Q \ w {\ mathcal {E} }(G)}$
mnożenie przez skalar jest zdefiniowane przez:
- ${\ Displaystyle 0 \ cdot P: = \ pusty zbiór \ qquad P \ w {\ mathcal {E}} (G)}$
- ${\ Displaystyle 1 \ cdot P: = P \ qquad P \ w {\ mathcal {E}} (G)}$

Podzbiory singletonowe E tworzą podstawę dla $mathcal {E}} (G)}$ \ .

Można również pomyśleć o $zbiorze$ potęg V utworzonym w przestrzeni wektorowej z podobnym dodawaniem wektorów i mnożeniem przez skalar, $\ styl wyświetlania {\ mathcal {E}} (G)}$ .

Nieruchomości

Macierz częstości dla wykresu definiuje jedną możliwą transformację liniową $}$ $displaystyle H$

{\ Displaystyle H: {\ mathcal {E}} (G) \ do {\ mathcal {V}} (G)}

między przestrzenią krawędzi a przestrzenią wierzchołków sol ${\ displaystyle G$ . Macierz częstości $incydentne$ jako transformacja liniowa, odwzorowuje każdą krawędź na jej dwa wierzchołki . Niech wtedy będzie krawędź między $\$ $displaystyle v}$ i $displaystyle u}$

{\ Displaystyle H (vu) = v + u}

Przestrzeń cyklu i przestrzeń cięcia są liniowymi podprzestrzeniami przestrzeni krawędzi.

Diestel, Reinhard (2005), Graph Theory (wyd. 3), Springer , ISBN 3-540-26182-6 (trzecie wydanie elektroniczne jest bezpłatnie dostępne na stronie autora).

Zobacz też