| dbo:abstract
|
- In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle. A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph K4, or a triangular book K1,1,n. Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect. By similar reasoning, every line perfect graph is a parity graph, a Meyniel graph, and a perfectly orderable graph. Line perfect graphs generalize the bipartite graphs, and share with them the properties that the maximum matching and minimum vertex cover have the same size, and that the chromatic index equals the maximum degree. (en)
- Рёберно совершенный граф — это граф, рёберный граф которого является совершенным. Эквивалентно, это графы, у которых каждый простой цикл нечётной длины является треугольником. Граф является рёберно совершенным тогда и только тогда, когда любая из его двусвязных компонент является двудольным графом, полным графом или книгой треугольников . Поскольку эти три типа двусвязных компонент являются сами по себе совершенными графами, любой рёберно совершенный граф сам совершенен. По аналогичным причинам любой рёберно совершенный граф является графом чётности, графом Мейнеля и вполне упорядочиваемым графом. Рёберно совершенные графы обобщают двудольные графы и разделяют с ними свойства, что наибольшее паросочетание и наименьшее вершинное покрытие имеют одинаковые размеры, а хроматический индекс равен максимальной степени. (ru)
- 在图论中，线完美图(line perfect graph)是其线图为的图。同样的，这些图中每个奇数长度的简单环都是一个三角形。 当且仅当一个图的任意都是二分图、完全图或三角形书 时，该图被称为线完美的，因为这三种类型的双连接组件本身是完美图，其形成的线图本身是完美的。 通过类似的推理，所有的线完美图都是、和. 线完美图推广了二部图，并与二部图共同拥有最大匹配和有相同尺寸以及色指数等于最大度的性质。 (zh)
- Реберно-досконалий граф — це граф, реберний граф якого є досконалим. Еквівалентно, це графи, у яких кожен простий цикл непарної довжини є трикутником. Граф є реберно досконалим тоді і тільки тоді, коли будь-яка з його двозв'язних компонент є двочастковим графом, повним графом або книгою трикутників . Оскільки ці три типи двозв'язних компонент самі є досконалими графами, будь-який реберно-досконалий граф сам досконалий. З тієї ж причини будь-який реберно-досконалий граф є графом парності, графом Мейнеля і цілком упорядковуваним графом. Реберно-досконалі графи узагальнюють двочасткові графи і поділяють з ними властивості, що найбільше парування і найменше вершинне покриття мають однакові розміри, а хроматичний індекс дорівнює найбільшому степеню. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3399 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- 在图论中，线完美图(line perfect graph)是其线图为的图。同样的，这些图中每个奇数长度的简单环都是一个三角形。 当且仅当一个图的任意都是二分图、完全图或三角形书 时，该图被称为线完美的，因为这三种类型的双连接组件本身是完美图，其形成的线图本身是完美的。 通过类似的推理，所有的线完美图都是、和. 线完美图推广了二部图，并与二部图共同拥有最大匹配和有相同尺寸以及色指数等于最大度的性质。 (zh)
- In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle. A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph K4, or a triangular book K1,1,n. Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect. By similar reasoning, every line perfect graph is a parity graph, a Meyniel graph, and a perfectly orderable graph. (en)
- Рёберно совершенный граф — это граф, рёберный граф которого является совершенным. Эквивалентно, это графы, у которых каждый простой цикл нечётной длины является треугольником. Граф является рёберно совершенным тогда и только тогда, когда любая из его двусвязных компонент является двудольным графом, полным графом или книгой треугольников . Поскольку эти три типа двусвязных компонент являются сами по себе совершенными графами, любой рёберно совершенный граф сам совершенен. По аналогичным причинам любой рёберно совершенный граф является графом чётности, графом Мейнеля и вполне упорядочиваемым графом. (ru)
- Реберно-досконалий граф — це граф, реберний граф якого є досконалим. Еквівалентно, це графи, у яких кожен простий цикл непарної довжини є трикутником. Граф є реберно досконалим тоді і тільки тоді, коли будь-яка з його двозв'язних компонент є двочастковим графом, повним графом або книгою трикутників . Оскільки ці три типи двозв'язних компонент самі є досконалими графами, будь-який реберно-досконалий граф сам досконалий. З тієї ж причини будь-який реберно-досконалий граф є графом парності, графом Мейнеля і цілком упорядковуваним графом. (uk)
|
| rdfs:label
|
- Line perfect graph (en)
- Рёберно совершенный граф (ru)
- 线完美图 (zh)
- Реберно-досконалий граф (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
