Kograf () – graf, który można zbudować z pojedynczych wierzchołków za pomocą operacji złączenia oraz sumowania grafów. Złączenie grafów G i F to graf powstały poprzez połączenie wszystkich wierzchołków grafu G z wszystkimi wierzchołkami grafu F, przy zachowaniu wewnętrznej budowy grafów G i F. Natomiast operacja sumy grafów to zwykłe sumowanie zbiorów krawędzi i wierzchołków.
Kografy można wygodnie reprezentować za pomocą kodrzewa (), którego liśćmi są wierzchołki grafów, natomiast węzły wewnętrzne drzewa reprezentują operację złączenia (1) i sumowania (0).
frame|center|Kograf wraz z kodrzewem.
Własności kografów średnica mniejsza od 3. nie zawierają ścieżki P4 jako podgrafu, stąd druga nazwa tej klasy grafów: P4-free. każdy podgraf indukowany kografu jest kografem. budowanie kodrzewa można wykonać w czasie liniowym.
Linki zewnętrzne [dostęp 2025-10-12]. Cograph , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-10-12].
Kategoria:Klasy grafów