翻訳と辞書 Words near each other ・ Cogolin ・ Cogollo del Cengio ・ Cogollor ・ Cogollos ・ Cogollos de Guadix ・ Cogollos Vega ・ Cogolludo ・ Cogon, Tagbilaran ・ Cogora ・ Cogorno ・ Cogoti La Pelicana Airport ・ Cogotí River ・ CogPrints ・ Cogra Bay, New South Wales ・ Cogra Moss ・ Cograph ・ Cogry ・ COGS ・ Cogs (video game) ・ Cogs, Wheels & Lovers ・ Cogset ・ Cogshall ・ Cogshall (mango) ・ Cogshall Hall ・ Cogswell ・ Cogswell Dam ・ Cogswell Interchange ・ Cogswell Polytechnical College ・ Cogswell Society ・ Cogswell Tower Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Cograph ： ウィキペディア英語版 Cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 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. Cographs have been discovered independently by several authors since the 1970s; early references include , , , and . They have also been called D *-graphs , hereditary Dacey graphs (after the related work of James C. Dacey, Jr. on orthomodular lattices; see ), and 2-parity graphs . See, e.g., for more detailed coverage of cographs, including the facts presented here. == Definition and characterization == Any cograph may be constructed using the following rules: # any single vertex graph is a cograph; # if $G$ is a cograph, so is its complement $\backslash overline$; # if $G$ and $H$ are cographs, so is their disjoint union $G\backslash cup\; H$. Several alternative characterizations of cographs can be given. Among them: * A cograph is a graph which does not contain the path ''P''4 on 4 vertices (and hence of length 3) as an induced subgraph. That is, a graph is a cograph if and only if for any four vertices $v\_1,v\_2,v\_3,v\_4$, if $\backslash ,\backslash$ and $\backslash$ are edges of the graph then at least one of $\backslash ,\backslash$ or $\backslash$ is also an edge . * A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex. * A cograph is a graph in which every nontrivial induced subgraph has at least two vertices with the same neighbourhoods. * A cograph is a graph in which every connected induced subgraph has a disconnected complement. * A cograph is a graph all of whose connected induced subgraphs have diameter at most 2. * A cograph is a graph in which every connected component is a distance-hereditary graph with diameter at most 2. * A cograph is a graph with clique-width at most 2 . * A cograph is a comparability graph of a series-parallel partial order . * A cograph is a permutation graph of a separable permutation . * A cograph is a graph all of whose minimal chordal completions are trivially perfect graphs . All complete graphs, complete bipartite graphs, threshold graphs, and Turán graphs are cographs. Every cograph is distance-hereditary, a comparability graph, and perfect. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cograph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.