Ptolemaic graph (original) (raw)
En théorie des graphes, un graphe de Ptolémée ou graphe ptolémaïque est un graphe non orienté dont les distances des plus courts chemins entre sommets les plus courtes obéissent à l'inégalité de Ptolémée, qui à son tour a été nommée d'après l'astronome et mathématicien grec Ptolémée. Les graphes de Ptolémée sont exactement les graphes qui sont à la fois cordaux et à distance héréditaire ; ils incluent les graphes par blocs et sont une sous-classe des graphes parfaits.
Property | Value |
---|---|
dbo:abstract | En théorie des graphes, un graphe de Ptolémée ou graphe ptolémaïque est un graphe non orienté dont les distances des plus courts chemins entre sommets les plus courtes obéissent à l'inégalité de Ptolémée, qui à son tour a été nommée d'après l'astronome et mathématicien grec Ptolémée. Les graphes de Ptolémée sont exactement les graphes qui sont à la fois cordaux et à distance héréditaire ; ils incluent les graphes par blocs et sont une sous-classe des graphes parfaits. (fr) In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs. (en) Птолеме́ев граф — это неориентированный граф, в котором расстояния по кратчайшему пути удовлетворяют неравенству Птолемея.Птолемеевы графы — это в точности графы, которые одновременно являются и хордальными, и дистанционно наследуемыми.Эти графы включают блоковые графы и являются подклассом совершенных графов. (ru) У теорії графів птолеме́їв граф — це неорієнтований граф, у якому відстані по найкоротшому шляху задовольняють нерівності Птолемея (грецького астронома і математика Птолемея). Птолемеєві графи — це точно графи, які одночасно є і хордальними, і дистанційно-успадковуваними. Ці графи включають блокові графи і є підкласом досконалих графів. (uk) |
dbo:thumbnail | wiki-commons:Special:FilePath/Identity_graph2.svg?width=300 |
dbo:wikiPageID | 50730814 (xsd:integer) |
dbo:wikiPageLength | 7526 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1079076784 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Ptolemy dbr:Antimatroid dbc:Graph_families dbc:Perfect_graphs dbr:Cycle_(graph_theory) dbr:Undirected_graph dbr:Vertex_separator dbr:Induced_subgraph dbr:Ptolemy's_inequality dbr:Generating_function dbr:Linear_time dbr:Shortest_path dbr:Perfect_graph dbr:Mathematician dbr:Graph_theory dbr:Roman_Greece dbr:Astronomer dbr:Covering_relation dbr:Chordal_graph dbr:Block_graph dbc:Intersection_classes_of_graphs dbr:Symbolic_method_(combinatorics) dbr:Distance-hereditary_graph dbr:Polytree dbr:Vertex_(graph_theory) dbr:Maximal_clique dbr:Induced_cycle dbr:Gem_graph dbr:File:Block_graph.svg dbr:File:Graph00001.svg dbr:File:Identity_graph2.svg dbr:File:Distance-hereditary_construction.svg |
dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:OEIS dbt:Reflist |
dcterms:subject | dbc:Graph_families dbc:Perfect_graphs dbc:Intersection_classes_of_graphs |
rdfs:comment | En théorie des graphes, un graphe de Ptolémée ou graphe ptolémaïque est un graphe non orienté dont les distances des plus courts chemins entre sommets les plus courtes obéissent à l'inégalité de Ptolémée, qui à son tour a été nommée d'après l'astronome et mathématicien grec Ptolémée. Les graphes de Ptolémée sont exactement les graphes qui sont à la fois cordaux et à distance héréditaire ; ils incluent les graphes par blocs et sont une sous-classe des graphes parfaits. (fr) In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs. (en) Птолеме́ев граф — это неориентированный граф, в котором расстояния по кратчайшему пути удовлетворяют неравенству Птолемея.Птолемеевы графы — это в точности графы, которые одновременно являются и хордальными, и дистанционно наследуемыми.Эти графы включают блоковые графы и являются подклассом совершенных графов. (ru) У теорії графів птолеме́їв граф — це неорієнтований граф, у якому відстані по найкоротшому шляху задовольняють нерівності Птолемея (грецького астронома і математика Птолемея). Птолемеєві графи — це точно графи, які одночасно є і хордальними, і дистанційно-успадковуваними. Ці графи включають блокові графи і є підкласом досконалих графів. (uk) |
rdfs:label | Graphe ptolémaïque (fr) Ptolemaic graph (en) Птолемеев граф (ru) Птолемеїв граф (uk) |
owl:sameAs | wikidata:Ptolemaic graph dbpedia-fr:Ptolemaic graph dbpedia-ru:Ptolemaic graph dbpedia-uk:Ptolemaic graph https://global.dbpedia.org/id/2LWDz yago-res:Ptolemaic graph |
prov:wasDerivedFrom | wikipedia-en:Ptolemaic_graph?oldid=1079076784&ns=0 |
foaf:depiction | wiki-commons:Special:FilePath/Graph00001.svg wiki-commons:Special:FilePath/Identity_graph2.svg wiki-commons:Special:FilePath/Distance-hereditary_construction.svg wiki-commons:Special:FilePath/Block_graph.svg |
foaf:isPrimaryTopicOf | wikipedia-en:Ptolemaic_graph |
is dbo:wikiPageWikiLink of | dbr:Ptolemy dbr:Antimatroid dbr:Ptolemy's_inequality dbr:Perfect_graph dbr:Trivially_perfect_graph dbr:Chordal_graph dbr:Block_graph dbr:Distance-hereditary_graph dbr:Longest_path_problem |
is foaf:primaryTopic of | wikipedia-en:Ptolemaic_graph |