Dopełnienie grafu

[Fretkonur01]

Czy możemy rozważać dopełnienie grafu, który nie jest grafem prostym, np wtedy gdy ma pętle albo krawędzie wielokrotne? Czy dopełnienie tyczy się wyłącznie grafów prostych? Proszę o wyjaśnienie tego zagadnienia.

[givrox7]

Nazwa "dopełnienie grafu" bierze się od "dopełnienia zbioru".
Jakikolwiek z wymienionych przez Ciebie rodzajów grafów definiuje się jako niepusty zbiór wierzchołków \(\displaystyle{ V}\) oraz (multi)zbiór krawędzi \(\displaystyle{ E}\).

Dopełnienie grafu \(\displaystyle{ (V, E)}\) definiuje się po prostu jako graf \(\displaystyle{ (V, \overline{E})}\), gdzie \(\displaystyle{ \overline{E}}\) to dopełnienie zbioru \(\displaystyle{ E}\) w przestrzeni wszystkich dopuszczalnych krawędzi.
\(\displaystyle{ \overline{E} = U \setminus E}\)

W przypadku multizbioru dopełnienie interpretuje się jako zbiór elementów, które ani razu nie występują w multizbiorze. (to jest moja interpretacja, ale ma sens)

Dla grafu skierowanego, \(\displaystyle{ E}\) zawiera pary wierzchołków, dlatego przestrzenią, w której liczymy dopełnienie, będzie zbiór wszystkich par różnych wierzchołków \(\displaystyle{ U = \{(x, y): x, y \in V \wedge x \neq y\}}\)

Dla grafu z pętlami przestrzenią, w której liczymy dopełnienie, będzie zbiór wszystkich dwuelementowych oraz jednoelementowych zbiorów wierzchołków \(\displaystyle{ U = \{\{x, y\}: x, y \in V \wedge x \neq y\} \cup \{\{x\}: x \in V\}}\)

Dla grafu z powielonymi krawędziami mamy multizbiór, który już omówiłem. \(\displaystyle{ U = \{\{x, y\}: x, y \in V \wedge x \neq y\}}\) ()

Mam nadzieję, że pomogłem