Kograf
Sign in to saveAlso known as complement-reducible graph, P4-free graph
thumb|The Turán graph T(13,4) is a cograph In graph theory, a cograph, or complement-reducible graph, or '''P4-free graph', is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K''1 and is closed under complementation and disjoint union.
Wikidata facts
- Image
- Complete bipartite graph K3,2.svg
Show 3 more facts
- studied by
- graph theory
- maintained by WikiProject
- WikiProject Mathematics
- Stack Exchange tag
- cstheory.stackexchange.com/tags/cograph
Sources (2)
via Wikidata · CC0
Article · Polski
Kograf (ang. cograph, P4-free graph) – graf, który można zbudować z pojedynczych wierzchołków za pomocą operacji oraz . 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ą (ang. cotree), którego liśćmi są wierzchołki grafów, natomiast węzły wewnętrzne drzewa reprezentują operację złączenia (1) i sumowania (0).
Abstract from DBpedia / Wikipedia · CC BY-SA