http://pco.iis.nsk.su/grapp/index.php?title=Chordal_graph&feed=atom&action=history Chordal graph - История изменений 2024-03-29T15:24:08Z История изменений этой страницы в вики MediaWiki 1.39.3 http://pco.iis.nsk.su/grapp/index.php?title=Chordal_graph&diff=10344&oldid=prev KEV в 11:12, 28 марта 2013 2013-03-28T11:12:42Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 18:12, 28 марта 2013</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Chordal graph&#039;&#039;&#039; <del style="font-weight: bold; text-decoration: none;">--- </del>хордальный граф.  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Chordal graph&#039;&#039;&#039; <ins style="font-weight: bold; text-decoration: none;">— [[</ins>хордальный граф<ins style="font-weight: bold; text-decoration: none;">]]</ins>.  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>A graph that does not contain &#039;&#039;chordless cycles&#039;&#039; of length greater</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>A <ins style="font-weight: bold; text-decoration: none;">[[</ins>graph<ins style="font-weight: bold; text-decoration: none;">, undirected graph, nonoriented graph|graph]] </ins>that does not contain &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[chordless cycle|</ins>chordless cycles<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039; of length greater than three is called a &#039;&#039;&#039;chordal&#039;&#039;&#039; graph. This is equivalent to saying that the graph does not contain an &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[induced (with vertices) subgraph|</ins>induced subgraph<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039; isomorphic to &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>C_{n}&lt;/math&gt; (i.e., a cycle of length &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>n&lt;/math&gt;) for &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>n &gt; 3&lt;/math&gt;.</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>than three is called a &#039;&#039;&#039;chordal&#039;&#039;&#039; graph. This is equivalent to saying that the graph does not</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>contain an &#039;&#039; induced subgraph&#039;&#039; isomorphic to &lt;math&gt;C_{n}&lt;/math&gt; (i.e., a cycle</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>of length &lt;math&gt;n&lt;/math&gt;) for &lt;math&gt;n &gt; 3&lt;/math&gt;.</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>There are many ways to characterize chordal graphs. Although many of</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>There are many ways to characterize chordal graphs. Although many of</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>these characterizations are interesting and useful, it suffices to</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>these characterizations are interesting and useful, it suffices to</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>list only some of them. One of the most important tools is the concept</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>list only some of them. One of the most important tools is the concept</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>of a &#039;&#039;perfect elimination scheme&#039;&#039;. The other way to define a chordal</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>of a &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[</ins>perfect elimination scheme<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;. The other way to define a chordal</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>graph is to consider it as an &#039;&#039;intersection graph&#039;&#039; of a family of</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>graph is to consider it as an &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[</ins>intersection graph<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039; of a family of</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>subtrees of a tree.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[subtree|</ins>subtrees<ins style="font-weight: bold; text-decoration: none;">]] </ins>of a <ins style="font-weight: bold; text-decoration: none;">[[</ins>tree<ins style="font-weight: bold; text-decoration: none;">]]</ins>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>An important subclass of chordal graphs is the &#039;&#039;interval</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>An important subclass of chordal graphs is the &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[interval graph|</ins>interval graphs<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;.</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>graphs&#039;&#039;.</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Other names of a chordal graph are &#039;&#039;&#039;Triangulated graph, Rigid circuit graph, Perfect elimination graph, Monotone transitive graph&#039;&#039;&#039;.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Other names of a chordal graph are &#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[</ins>Triangulated graph<ins style="font-weight: bold; text-decoration: none;">]]</ins>, <ins style="font-weight: bold; text-decoration: none;">[[</ins>Rigid circuit graph<ins style="font-weight: bold; text-decoration: none;">]]</ins>, <ins style="font-weight: bold; text-decoration: none;">[[</ins>Perfect elimination graph<ins style="font-weight: bold; text-decoration: none;">]]</ins>, <ins style="font-weight: bold; text-decoration: none;">[[</ins>Monotone transitive graph<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Литература==</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009</ins>.</div></td></tr> </table> KEV http://pco.iis.nsk.su/grapp/index.php?title=Chordal_graph&diff=6477&oldid=prev Glk: Новая страница: «'''Chordal graph''' --- хордальный граф. A graph that does not contain ''chordless cycles'' of length greater than three is called a '''chordal''' gr…» 2011-03-02T06:01:05Z <p>Новая страница: «&#039;&#039;&#039;Chordal graph&#039;&#039;&#039; --- хордальный граф. A graph that does not contain &#039;&#039;chordless cycles&#039;&#039; of length greater than three is called a &#039;&#039;&#039;chordal&#039;&#039;&#039; gr…»</p> <p><b>Новая страница</b></p><div>&#039;&#039;&#039;Chordal graph&#039;&#039;&#039; --- хордальный граф. <br /> <br /> A graph that does not contain &#039;&#039;chordless cycles&#039;&#039; of length greater<br /> than three is called a &#039;&#039;&#039;chordal&#039;&#039;&#039; graph. This is equivalent to saying that the graph does not<br /> contain an &#039;&#039; induced subgraph&#039;&#039; isomorphic to &lt;math&gt;C_{n}&lt;/math&gt; (i.e., a cycle<br /> of length &lt;math&gt;n&lt;/math&gt;) for &lt;math&gt;n &gt; 3&lt;/math&gt;.<br /> <br /> There are many ways to characterize chordal graphs. Although many of<br /> these characterizations are interesting and useful, it suffices to<br /> list only some of them. One of the most important tools is the concept<br /> of a &#039;&#039;perfect elimination scheme&#039;&#039;. The other way to define a chordal<br /> graph is to consider it as an &#039;&#039;intersection graph&#039;&#039; of a family of<br /> subtrees of a tree.<br /> <br /> An important subclass of chordal graphs is the &#039;&#039;interval<br /> graphs&#039;&#039;.<br /> <br /> Other names of a chordal graph are &#039;&#039;&#039;Triangulated graph, Rigid circuit graph, Perfect elimination graph, Monotone transitive graph&#039;&#039;&#039;.</div> Glk