dbo:abstract
|
- In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords (edges connecting non-consecutive vertices of the cycle). The chords may be uncrossed (as shown in the figure) or they may cross each other, as long as there are at least two of them. The Meyniel graphs are named after Henri Meyniel (also known for Meyniel's conjecture), who proved that they are perfect graphs in 1976, long before the proof of the strong perfect graph theorem completely characterized the perfect graphs.The same result was independently discovered by . (en)
- Граф Мейнеля — это граф, в котором любой нечётный цикл длины пять и более имеет по меньшей мере две хорды, то есть два ребра, соединяющих несоседние вершины цикла. Хорды могут быть непересекающимися (как на рисунке), а могут и пересекаться. Графы Мейнеля названы именем Генри Мейнеля (известного также по гипотезе Мейнеля), который доказал в 1976 году, что они являются совершенными графами задолго до доказательства cильной гипотезы о совершенных графах, полностью описывающей совершенные графы. Тот же результат был независимо обнаружен Маркосяном и Карапетяном. (ru)
- Граф Мейнеля — це граф, у якому будь-який непарний цикл довжини п'ять і більше має принаймні дві хорди, тобто два ребра, що з'єднують несусідні вершини циклу. Хорди можуть бути такими, що не перетинаються (як на малюнку), а можуть і перетинатися. Графи Мейнеля названо ім'ям (відомого також за гіпотезою Мейнеля), який 1976 року довів, що вони є досконалими графами задовго до доведення сильної теореми про досконалі графи, яка повністю описує досконалі графи. Той самий результат незалежно виявили Маркосян і Карапетян. (uk)
|
dbo:thumbnail
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 4935 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
dbp:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords (edges connecting non-consecutive vertices of the cycle). The chords may be uncrossed (as shown in the figure) or they may cross each other, as long as there are at least two of them. The Meyniel graphs are named after Henri Meyniel (also known for Meyniel's conjecture), who proved that they are perfect graphs in 1976, long before the proof of the strong perfect graph theorem completely characterized the perfect graphs.The same result was independently discovered by . (en)
- Граф Мейнеля — это граф, в котором любой нечётный цикл длины пять и более имеет по меньшей мере две хорды, то есть два ребра, соединяющих несоседние вершины цикла. Хорды могут быть непересекающимися (как на рисунке), а могут и пересекаться. Графы Мейнеля названы именем Генри Мейнеля (известного также по гипотезе Мейнеля), который доказал в 1976 году, что они являются совершенными графами задолго до доказательства cильной гипотезы о совершенных графах, полностью описывающей совершенные графы. Тот же результат был независимо обнаружен Маркосяном и Карапетяном. (ru)
- Граф Мейнеля — це граф, у якому будь-який непарний цикл довжини п'ять і більше має принаймні дві хорди, тобто два ребра, що з'єднують несусідні вершини циклу. Хорди можуть бути такими, що не перетинаються (як на малюнку), а можуть і перетинатися. Графи Мейнеля названо ім'ям (відомого також за гіпотезою Мейнеля), який 1976 року довів, що вони є досконалими графами задовго до доведення сильної теореми про досконалі графи, яка повністю описує досконалі графи. Той самий результат незалежно виявили Маркосян і Карапетян. (uk)
|
rdfs:label
|
- Meyniel graph (en)
- Граф Мейнеля (ru)
- Граф Мейнеля (uk)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:depiction
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageWikiLink
of | |
is foaf:primaryTopic
of | |