Trivially perfect graph (original) (raw)
En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S. Wolk en 1962; ils ont été nommés ainsi par Golumbic ; Golumbic écrit que « le nom a été choisi car il est trivial de montrer qu'un tel graphique est parfait ». Les graphes trivialement parfaits sont également appelés graphes de comparabilité d'arbres, graphes de comparabilité arborescents, et graphes à quasi-seuil.
| Property | Value |
|---|---|
| dbo:abstract | En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S. Wolk en 1962; ils ont été nommés ainsi par Golumbic ; Golumbic écrit que « le nom a été choisi car il est trivial de montrer qu'un tel graphique est parfait ». Les graphes trivialement parfaits sont également appelés graphes de comparabilité d'arbres, graphes de comparabilité arborescents, et graphes à quasi-seuil. (fr) In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by (Wolk , ) but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs. (en) Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик. Тривиально совершенные графы первым изучал Волк, но название дал Голумбик. Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными.» Тривиально совершенные графы известны также как графы сравнимости деревьев, древовидные графы сравнимости и квазипороговые графы. (ru) Тривіально досконалий граф — це граф із властивістю, що в кожному його породженому підграфі розмір найбільшої (за розміром) незалежної множини дорівнює числу найбільших клік. Тривіально досконалі графи першим вивчав Волк, але назву дав Голумбік. Голумбік писав, що «цю назву вибрано з огляду на тривіальність доведення, що такі графи є досконалими». Тривіально досконалі графи відомі також як графи порівнянності дерев, деревовидні графи порівнянності і квазіпорогові графи. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Trivially_perfect_graph.svg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/graphclassessurv0000bran http://www.graphclasses.org/classes/gc_327.html |
| dbo:wikiPageID | 18033364 (xsd:integer) |
| dbo:wikiPageLength | 10836 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096466892 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_families dbc:Perfect_graphs dbr:Path_graph dbr:Relation_(mathematics) dbr:Induced_path dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:Lexicographic_breadth-first_search dbr:Ptolemaic_graph dbr:Chromatic_number dbr:NP-complete dbr:Linear_time dbr:Clique_number dbr:Comparability_graph dbr:Complement_graph dbr:Perfect_graph dbr:Proceedings_of_the_American_Mathematical_Society dbr:Stack-sortable_permutation dbr:Tree_(set_theory) dbr:Windmill_graph dbr:Cycle_graph dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Interval_(mathematics) dbr:Interval_graph dbr:Chordal_graph dbr:Big_O_notation dbr:Cograph dbr:Threshold_graph dbr:Neighborhood_(graph_theory) dbr:Universal_vertex dbr:Maximal_clique dbr:Partial_order dbr:Permutation_graph dbr:Maximum_independent_set dbr:Clique_cover_number dbr:Well-ordered dbr:File:Trivially_perfect_graph.svg dbr:Pseudo-Grundy_number |
| dbp:last | Wolk (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sub dbt:Sup dbt:Harvs |
| dbp:year | 1962 (xsd:integer) 1965 (xsd:integer) |
| dct:subject | dbc:Graph_families dbc:Perfect_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S. Wolk en 1962; ils ont été nommés ainsi par Golumbic ; Golumbic écrit que « le nom a été choisi car il est trivial de montrer qu'un tel graphique est parfait ». Les graphes trivialement parfaits sont également appelés graphes de comparabilité d'arbres, graphes de comparabilité arborescents, et graphes à quasi-seuil. (fr) In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by (Wolk , ) but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs. (en) Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик. Тривиально совершенные графы первым изучал Волк, но название дал Голумбик. Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными.» Тривиально совершенные графы известны также как графы сравнимости деревьев, древовидные графы сравнимости и квазипороговые графы. (ru) Тривіально досконалий граф — це граф із властивістю, що в кожному його породженому підграфі розмір найбільшої (за розміром) незалежної множини дорівнює числу найбільших клік. Тривіально досконалі графи першим вивчав Волк, але назву дав Голумбік. Голумбік писав, що «цю назву вибрано з огляду на тривіальність доведення, що такі графи є досконалими». Тривіально досконалі графи відомі також як графи порівнянності дерев, деревовидні графи порівнянності і квазіпорогові графи. (uk) |
| rdfs:label | Graphe trivialement parfait (fr) Тривиально совершенный граф (ru) Trivially perfect graph (en) Тривіально досконалий граф (uk) |
| owl:sameAs | freebase:Trivially perfect graph yago-res:Trivially perfect graph wikidata:Trivially perfect graph dbpedia-fr:Trivially perfect graph dbpedia-ru:Trivially perfect graph dbpedia-uk:Trivially perfect graph https://global.dbpedia.org/id/4wvMe |
| prov:wasDerivedFrom | wikipedia-en:Trivially_perfect_graph?oldid=1096466892&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Trivially_perfect_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Trivially_perfect_graph |
| is dbo:wikiPageRedirects of | dbr:Comparability_graph_of_trees dbr:Comparability_graphs_of_trees dbr:Aborescent_comparability_graph dbr:Quasi-threshold_graph |
| is dbo:wikiPageWikiLink of | dbr:Indifference_graph dbr:Induced_path dbr:Comparability_graph_of_trees dbr:Comparability_graphs_of_trees dbr:Chordal_completion dbr:Comparability_graph dbr:Perfect_graph dbr:Planar_separator_theorem dbr:Stack-sortable_permutation dbr:Tree_(set_theory) dbr:Windmill_graph dbr:Aborescent_comparability_graph dbr:Forbidden_graph_characterization dbr:Tree-depth dbr:Interval_graph dbr:Cograph dbr:Threshold_graph dbr:Distance-hereditary_graph dbr:Universal_vertex dbr:Quasi-threshold_graph |
| is foaf:primaryTopic of | wikipedia-en:Trivially_perfect_graph |
