rdfs:comment
| - In der Informatik ist ein Co-Graph ein ungerichteter Graph , welcher sich mit bestimmten elementaren Operationen konstruieren lässt. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE sowie KNOTENÜBERDECKUNG in Linearzeit lösen. (de)
- Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. (fr)
- 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). (pl)
- 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 K1 and is closed under complementation and disjoint union. Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. The cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs. (en)
- В теорії графів кограф, або додатково звідний граф, чи граф, вільний від P4, — це граф, який можна отримати з графа з єдиною вершиною K1 операціями доповнення та об'єднання графів. Таким чином, сімейство кографів — це найменший клас графів, що містить K1 і замкнутий відносно доповнення та об'єднання. В книзі Брандштедта, Лі і Шпінрада кографи розглянуто детальніше, включно з фактами, наведеними тут. (uk)
- В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения. Смотрите книгу Брандштедта, Ли и Шпинрада, где кографы рассмотрены более детально, включая факты, приведённые здесь. (ru)
|