Dopełnienie grafu
-
- Użytkownik
- Posty: 3
- Rejestracja: 31 maja 2021, o 18:50
- Płeć: Mężczyzna
- wiek: 24
Dopełnienie grafu
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.
Re: Dopełnienie grafu
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
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
Ostatnio zmieniony 17 paź 2021, o 10:47 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.