Dopełnienie grafu: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
WP:SK, źródła/przypisy |
m przecinek, replaced: wtedy gdy → wtedy, gdy przy użyciu AWB |
||
Linia 2:
{{Teoria grafów}}
'''Dopełnienie grafu''' ({{ang.|complement of graph}}) – [[graf (matematyka)|graf]] <math>\overline{G}</math>, zawierający te same wierzchołki co graf <math>G</math>, natomiast pomiędzy wierzchołkami grafu <math>\overline{G}</math> istnieje krawędź wtedy i tylko wtedy, gdy pomiędzy tymi wierzchołkami nie istnieje krawędź w grafie <math>G</math><ref>{{Cytuj książkę | nazwisko = Diestel | imię = Reinhard | tytuł = Graph Theory | url=http://diestel-graph-theory.com/index.html | miejsce = Nowy Jork | rok = 2000 | strony = 4| isbn= 0-387-95014-1}}</ref>.
== Konstrukcja formalna ==
Linia 12:
* Dopełnieniem n-wierzchołkowego grafu regularnego stopnia k jest n-wierzchołkowy graf regularny stopnia n-k-1.
* Dopełnieniem grafu pełnego jest graf nie zawierający krawędzi.
* Graf jest '''samodopełniający się''' gdy <math>G = \overline{G}</math>.
[[Plik:Complement graph sample.png|frame|left|
| |||