Graf krawędziowy
Graf krawędziowy, znany również jako graf L(G), jest skonstruowany na podstawie innego grafu G. W tym przypadku zbiór wierzchołków grafu F to zbiór krawędzi grafu G, a zbiór krawędzi grafu F składa się z par krawędzi z G.
Definicje
- Grafy nieskierowane: Wierzchołki {v1, v2} oraz {v3, v4} w grafie F są połączone, gdy zachodzi przynajmniej jedna z relacji: v1=v3, v1=v4, v2=v3 lub v2=v4.
- Grafy skierowane: Krawędź prowadzi od wierzchołka (v1, v2) do (v3, v4) w grafie F, gdy v2=v3.
Intuicyjnie, krawędzie grafu G traktowane są jako wierzchołki w grafie F. Wierzchołki grafu F łączone są krawędziami, gdy istnieje przejście między odpowiadającymi sobie krawędziami grafu G.
Właściwości grafów krawędziowych
Graf krawędziowy odnosi się głównie do grafów nieskierowanych. Istnieją pytania dotyczące tego, czy dany graf może być grafem krawędziowym innego grafu oraz czy każdy graf może być grafem krawędziowym jakiegoś innego grafu.
W 1968 roku Lowell W. Beineke udowodnił, że graf jest grafem krawędziowym innego grafu, jeśli i tylko jeśli nie zawiera jednego z dziewięciu specyficznych grafów.
- Graf krawędziowy grafu spójnego jest zawsze spójny.
- Indeks chromatyczny grafu G jest równy liczbie chromatycznej jego grafu krawędziowego: .
Podsumowanie
Graf krawędziowy jest istotnym pojęciem w teorii grafów, które pozwala na analizę relacji między krawędziami grafu G. Właściwości grafów krawędziowych, w tym ich spójność oraz indeksy chromatyczne, mają kluczowe znaczenie w badaniach nad strukturą grafów.
