Circular-arc graph (original) (raw)
Ein Kreisbogengraph ist in der Diskreten Mathematik eine Struktur der Graphentheorie. Sei ein Graph. Ist eine Familie von Kreisbögen zu einem festen Radius dergestalt, dass gilt so heißt Kreisbogenmodell für . Ein Graph ist genau dann ein Kreisbogengraph, wenn er ein Kreisbogenmodell besitzt. Kreisbogengraphen wurden ab den 1970er Jahren zuerst von und dann bald von vielen Weiteren untersucht.
| Property | Value |
|---|---|
| dbo:abstract | Ein Kreisbogengraph ist in der Diskreten Mathematik eine Struktur der Graphentheorie. Sei ein Graph. Ist eine Familie von Kreisbögen zu einem festen Radius dergestalt, dass gilt so heißt Kreisbogenmodell für . Ein Graph ist genau dann ein Kreisbogengraph, wenn er ein Kreisbogenmodell besitzt. Kreisbogengraphen wurden ab den 1970er Jahren zuerst von und dann bald von vielen Weiteren untersucht. (de) In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect. Formally, let be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where and A family of arcs that corresponds to G is called an arc model. (en) В теории графов графом дуг окружности называется граф пересечений множества дуг окружности. Граф имеет одну вершину для каждой дуги окружности и ребро между двумя вершинами, если соответствующие дуги пересекаются. Формально, пусть — множество дуг. Тогда соответствующий им граф дуг окружности — это G = (V, E), где и Семейство дуг, соответствующее графу G, называется дуговой моделью. (ru) У теорії графів графом дуг кола називають граф перетинів множини дуг кола. Граф має одну вершину для кожної дуги кола і ребро між двома вершинами, якщо відповідні дуги перетинаються. Формально, нехай — множина дуг. Тоді відповідний їм граф дуг кола — це G = (V, E), де і Сімейство дуг, відповідне графу G, називають дугового моделлю. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Circular-arc_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.graphclasses.org/index.html http://www.columbia.edu/~mc2775/claws3.pdf http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description%23description https://web.archive.org/web/20100522154759/http:/www.elsevier.com/wps/find/bookdescription.cws_home/699916/description%23description http://www.graphclasses.org/classes/gc_133.html |
| dbo:wikiPageID | 17502341 (xsd:integer) |
| dbo:wikiPageLength | 7348 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032209482 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithmica dbc:Geometric_graphs dbr:Resource_allocation dbr:SIAM_Journal_on_Computing dbr:Arc_(geometry) dbr:Claw-free_graph dbr:Helly_family dbr:Perfect_graph dbr:Edge_(graph_theory) dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Intersection_graph dbr:Interval_graph dbc:Intersection_classes_of_graphs dbr:Operations_research dbr:Vertex_(graph_theory) dbr:File:Circular-arc_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Reflist |
| dct:subject | dbc:Geometric_graphs dbc:Intersection_classes_of_graphs |
| rdf:type | yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Communication100033020 yago:Graph107000195 yago:Group100031264 yago:WikicatGeometricGraphs yago:WikicatIntersectionClassesOfGraphs yago:VisualCommunication106873252 |
| rdfs:comment | Ein Kreisbogengraph ist in der Diskreten Mathematik eine Struktur der Graphentheorie. Sei ein Graph. Ist eine Familie von Kreisbögen zu einem festen Radius dergestalt, dass gilt so heißt Kreisbogenmodell für . Ein Graph ist genau dann ein Kreisbogengraph, wenn er ein Kreisbogenmodell besitzt. Kreisbogengraphen wurden ab den 1970er Jahren zuerst von und dann bald von vielen Weiteren untersucht. (de) In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect. Formally, let be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where and A family of arcs that corresponds to G is called an arc model. (en) В теории графов графом дуг окружности называется граф пересечений множества дуг окружности. Граф имеет одну вершину для каждой дуги окружности и ребро между двумя вершинами, если соответствующие дуги пересекаются. Формально, пусть — множество дуг. Тогда соответствующий им граф дуг окружности — это G = (V, E), где и Семейство дуг, соответствующее графу G, называется дуговой моделью. (ru) У теорії графів графом дуг кола називають граф перетинів множини дуг кола. Граф має одну вершину для кожної дуги кола і ребро між двома вершинами, якщо відповідні дуги перетинаються. Формально, нехай — множина дуг. Тоді відповідний їм граф дуг кола — це G = (V, E), де і Сімейство дуг, відповідне графу G, називають дугового моделлю. (uk) |
| rdfs:label | Kreisbogengraph (de) Circular-arc graph (en) Граф дуг окружности (ru) Граф дуг кола (uk) |
| owl:sameAs | freebase:Circular-arc graph yago-res:Circular-arc graph wikidata:Circular-arc graph dbpedia-de:Circular-arc graph dbpedia-ru:Circular-arc graph dbpedia-uk:Circular-arc graph https://global.dbpedia.org/id/4hm2M |
| prov:wasDerivedFrom | wikipedia-en:Circular-arc_graph?oldid=1032209482&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Circular-arc_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Circular-arc_graph |
| is dbo:wikiPageRedirects of | dbr:Helly_circular-arc_graph dbr:Circular_arc_graph |
| is dbo:wikiPageWikiLink of | dbr:Pathwidth dbr:Intersection_number_(graph_theory) dbr:Claw-free_graph dbr:Femisphere dbr:Interval_graph dbr:Helly_circular-arc_graph dbr:Circular_arc dbr:Longest_path_problem dbr:Circular_arc_graph |
| is foaf:primaryTopic of | wikipedia-en:Circular-arc_graph |
