Kograf
Ten artykuł od 2016-06 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
Kograf (ang. cograph, P4-free graph) – 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 (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).
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.
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów |
|
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |