Intersection graph (original) (raw)
Průnikový graf je graf, kde vrcholům odpovídají množiny systému a hrany jsou právě mezi těmi, které mají neprázdný průnik. Kromě průnikových grafů obecných množinových systémů se zkoumají například průnikové grafy geometrických objektů, jako úseček na přímce, křivek či polygonů v rovině nebo koulí a obecných těles v prostoru libovolné dimenze.
| Property | Value |
|---|---|
| dbo:abstract | Průnikový graf je graf, kde vrcholům odpovídají množiny systému a hrany jsou právě mezi těmi, které mají neprázdný průnik. Kromě průnikových grafů obecných množinových systémů se zkoumají například průnikové grafy geometrických objektů, jako úseček na přímce, křivek či polygonů v rovině nebo koulí a obecných těles v prostoru libovolné dimenze. (cs) In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. (en) En teoría de grafos, dada una familia de conjuntos {Si}, se define su grafo de intersección como el grafo obtenido al representar cada conjunto Si por un vértice de modo que dos vértices sean adyacentes si y solo si los conjuntos que representan tienen intersección no vacía. Cualquier grafo G puede ser representado como grafo de intersección: para cada vértice vi de G, construiremos un conjunto Si formado por todas las aristas incidentes en vi; dos de estos conjuntos tendrán intersección no vacía si y solo si los vértices correspondientes a cada conjunto comparten una arista. Al restringir las familias de conjuntos a ciertos tipos, se obtienen las siguientes familias de grafos: * Grafo de intervalos, el grafo de intersección de intervalos de la recta real. * , grafo de intersección de arcos definidos sobre una misma circunferencia. * , una de sus caracterizaciones es la de ser grafo de intersección de subgrafos conexos de un árbol. (es) En théorie des graphes, un graphe d'intersection est un graphe représentant les intersections d'une famille d'ensembles. Plus précisément, pour une famille d'ensembles finie donnée, on associe à chaque ensemble un sommet, et deux sommets sont reliés par une arête si les ensembles ont une intersection non nulle. Beaucoup de familles de graphe sont définies par l'intersection d'ensembles géométriques, par exemple des sphères dans le plan, ou des intervalles sur une droite. Ces représentations géométriques permettent parfois d'avoir des algorithmes plus efficaces. (fr) В теорії графів графом перетинів називається граф, схему перетинів сімейства множин. Будь-який граф можна подати як граф перетинів, але деякі важливі спеціальні класи можна визначити за допомогою типів множин, що використовуються для подання у вигляді перетинів множин. Огляд теорії графів перетинів і важливих спеціальних класів графів перетинів наведено в книзі Маккі і Макморріса. (uk) В теории графов графом пересечений называется граф, схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств. Обзор теории графов пересечений и важных специальных классов графов пересечений смотрите в книге МакКи и МакМорриса. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Intersection_graph.gif?width=300 |
| dbo:wikiPageExternalLink | http://www.eprisner.de/Journey/Rahmen.html http://videolectures.net/sicgt07_kratochvil_gig/ http://ovid.cs.depaul.edu/documents/convex.pdf%7Ctitle= http://www.renyi.hu/~p_erdos/1966-21.pdf |
| dbo:wikiPageID | 7726759 (xsd:integer) |
| dbo:wikiPageLength | 8987 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110403354 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Biconnected_component dbr:Path_graph dbr:Undirected_graph dbr:Inclusion_order dbr:Indifference_graph dbr:Induced_subgraph dbr:International_Symposium_on_Graph_Drawing dbr:Intersection_number_(graph_theory) dbr:Line_segment dbr:Order_theory dbr:Graph_(discrete_mathematics) dbr:Boxicity dbr:Contact_graph dbr:Line_graph dbr:Clique_(graph_theory) dbr:Clique_graph dbr:Comparability_graph dbr:Complete_(complexity) dbr:Empty_set dbr:String_graph dbr:Tree_(graph_theory) dbr:Trapezoid_graph dbr:Graph_theory dbr:Intersection_(set_theory) dbr:Interval_graph dbr:Hyperrectangle dbr:Plane_curve dbr:Chordal_graph dbr:Block_graph dbc:Intersection_classes_of_graphs dbr:Planar_graph dbr:Poset dbr:Circle_graph dbr:Circle_packing_theorem dbr:Circular_arc dbr:If_and_only_if dbr:Set_(mathematics) dbr:Unit_disk_graph dbr:Existential_theory_of_the_reals dbr:Polygon-circle_graph dbr:Maximal_clique dbr:Permutation_graph dbr:Scheinerman's_conjecture dbr:Unit_disk dbr:Circular_arc_graph dbr:File:Intersection_graph.gif |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Math dbt:Mvar dbt:Sfrac dbt:Short_description dbt:Sub |
| dct:subject | dbc:Intersection_classes_of_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:WikicatParametricFamiliesOfGraphs yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | Průnikový graf je graf, kde vrcholům odpovídají množiny systému a hrany jsou právě mezi těmi, které mají neprázdný průnik. Kromě průnikových grafů obecných množinových systémů se zkoumají například průnikové grafy geometrických objektů, jako úseček na přímce, křivek či polygonů v rovině nebo koulí a obecných těles v prostoru libovolné dimenze. (cs) In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. (en) En théorie des graphes, un graphe d'intersection est un graphe représentant les intersections d'une famille d'ensembles. Plus précisément, pour une famille d'ensembles finie donnée, on associe à chaque ensemble un sommet, et deux sommets sont reliés par une arête si les ensembles ont une intersection non nulle. Beaucoup de familles de graphe sont définies par l'intersection d'ensembles géométriques, par exemple des sphères dans le plan, ou des intervalles sur une droite. Ces représentations géométriques permettent parfois d'avoir des algorithmes plus efficaces. (fr) В теорії графів графом перетинів називається граф, схему перетинів сімейства множин. Будь-який граф можна подати як граф перетинів, але деякі важливі спеціальні класи можна визначити за допомогою типів множин, що використовуються для подання у вигляді перетинів множин. Огляд теорії графів перетинів і важливих спеціальних класів графів перетинів наведено в книзі Маккі і Макморріса. (uk) В теории графов графом пересечений называется граф, схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств. Обзор теории графов пересечений и важных специальных классов графов пересечений смотрите в книге МакКи и МакМорриса. (ru) En teoría de grafos, dada una familia de conjuntos {Si}, se define su grafo de intersección como el grafo obtenido al representar cada conjunto Si por un vértice de modo que dos vértices sean adyacentes si y solo si los conjuntos que representan tienen intersección no vacía. Cualquier grafo G puede ser representado como grafo de intersección: para cada vértice vi de G, construiremos un conjunto Si formado por todas las aristas incidentes en vi; dos de estos conjuntos tendrán intersección no vacía si y solo si los vértices correspondientes a cada conjunto comparten una arista. (es) |
| rdfs:label | Průnikový graf (cs) Grafo de intersección (es) Graphe d'intersection (fr) Intersection graph (en) Граф пересечений (ru) Граф перетинів (uk) |
| owl:sameAs | freebase:Intersection graph yago-res:Intersection graph wikidata:Intersection graph dbpedia-cs:Intersection graph dbpedia-es:Intersection graph dbpedia-fa:Intersection graph dbpedia-fr:Intersection graph dbpedia-hu:Intersection graph dbpedia-ru:Intersection graph dbpedia-uk:Intersection graph https://global.dbpedia.org/id/3DaZh |
| prov:wasDerivedFrom | wikipedia-en:Intersection_graph?oldid=1110403354&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Intersection_graph.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Intersection_graph |
| is dbo:wikiPageRedirects of | dbr:Intersection_class_of_graphs |
| is dbo:wikiPageWikiLink of | dbr:Biconnected_component dbr:Bipartite_half dbr:Book_embedding dbr:Arc_diagram dbr:Pathwidth dbr:Regina_Tyshkevich dbr:Inclusion_order dbr:Independent_set_(graph_theory) dbr:Indifference_graph dbr:Intersection_number_(graph_theory) dbr:Interval_scheduling dbr:Penny_graph dbr:1-planar_graph dbr:Maximum_disjoint_set dbr:Geometric_graph_theory dbr:Rado_graph dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Bounded_expansion dbr:Boxicity dbr:Contact_graph dbr:Line_graph dbr:Chord_diagram_(mathematics) dbr:Claw-free_graph dbr:Clique_(graph_theory) dbr:Clique_graph dbr:Perfect_graph dbr:String_graph dbr:Tree_decomposition dbr:Well-covered_graph dbr:Fáry's_theorem dbr:Line_graph_of_a_hypergraph dbr:Locally_linear_graph dbr:Trapezoid_graph dbr:Erdős–Faber–Lovász_conjecture dbr:Outerplanar_graph dbr:Graph_drawing dbr:Graph_theory dbr:Schläfli_double_six dbr:Representation_(mathematics) dbr:Grötzsch's_theorem dbr:Interval_graph dbr:Jan_Kratochvíl dbr:Arrangement_of_lines dbr:Chordal_graph dbr:Bipartite_graph dbr:Block_graph dbr:Ed_Scheinerman dbr:Rectangle_packing dbr:Distance-hereditary_graph dbr:Map_graph dbr:Planar_graph dbr:Polygon_covering dbr:Split_graph dbr:Circle_graph dbr:Circle_packing dbr:Circle_packing_theorem dbr:Circular-arc_graph dbr:Fred_S._Roberts dbr:Implicit_graph dbr:Kissing_number dbr:Unit_disk_graph dbr:Schläfli_graph dbr:Existential_theory_of_the_reals dbr:Polygon-circle_graph dbr:Sierpiński_triangle dbr:Permutation_graph dbr:Χ-bounded dbr:Scheinerman's_conjecture dbr:Intersection_class_of_graphs |
| is foaf:primaryTopic of | wikipedia-en:Intersection_graph |
