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>'''Chordal graph''' <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>'''Chordal graph''' <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 ''chordless cycles'' 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 ''<ins style="font-weight: bold; text-decoration: none;">[[chordless cycle|</ins>chordless cycles<ins style="font-weight: bold; text-decoration: none;">]]</ins>'' of length greater than three is called a '''chordal''' graph. This is equivalent to saying that the graph does not contain an ''<ins style="font-weight: bold; text-decoration: none;">[[induced (with vertices) subgraph|</ins>induced subgraph<ins style="font-weight: bold; text-decoration: none;">]]</ins>'' isomorphic to <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>C_{n}</math> (i.e., a cycle of length <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>n</math>) for <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>n > 3</math>.</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 '''chordal''' 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 '' induced subgraph'' isomorphic to <math>C_{n}</math> (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 <math>n</math>) for <math>n > 3</math>.</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 ''perfect elimination scheme''. 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 ''<ins style="font-weight: bold; text-decoration: none;">[[</ins>perfect elimination scheme<ins style="font-weight: bold; text-decoration: none;">]]</ins>''. 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 ''intersection graph'' 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 ''<ins style="font-weight: bold; text-decoration: none;">[[</ins>intersection graph<ins style="font-weight: bold; text-decoration: none;">]]</ins>'' 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 ''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 ''<ins style="font-weight: bold; text-decoration: none;">[[interval graph|</ins>interval graphs<ins style="font-weight: bold; text-decoration: none;">]]</ins>''.</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''.</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 '''Triangulated graph, Rigid circuit graph, Perfect elimination graph, Monotone transitive graph'''.</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 '''<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>'''<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>Новая страница: «'''Chordal graph''' --- хордальный граф. A graph that does not contain ''chordless cycles'' of length greater than three is called a '''chordal''' gr…»</p>
<p><b>Новая страница</b></p><div>'''Chordal graph''' --- хордальный граф. <br />
<br />
A graph that does not contain ''chordless cycles'' of length greater<br />
than three is called a '''chordal''' graph. This is equivalent to saying that the graph does not<br />
contain an '' induced subgraph'' isomorphic to <math>C_{n}</math> (i.e., a cycle<br />
of length <math>n</math>) for <math>n > 3</math>.<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 ''perfect elimination scheme''. The other way to define a chordal<br />
graph is to consider it as an ''intersection graph'' of a family of<br />
subtrees of a tree.<br />
<br />
An important subclass of chordal graphs is the ''interval<br />
graphs''.<br />
<br />
Other names of a chordal graph are '''Triangulated graph, Rigid circuit graph, Perfect elimination graph, Monotone transitive graph'''.</div>
Glk