Line graph of a hypergraph (original) (raw)
In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraph H, denoted L(H), is the graph whose vertex set is the set of the hyperedges of H, with two vertices adjacent in L(H) when their corresponding hyperedges have a nonempty intersection in H. In other words, L(H) is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph. A hypergraph is linear if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, not only of some hypergraph, but of some linear hypergraph.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraph H, denoted L(H), is the graph whose vertex set is the set of the hyperedges of H, with two vertices adjacent in L(H) when their corresponding hyperedges have a nonempty intersection in H. In other words, L(H) is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph. Questions about line graphs of hypergraphs are often generalizations of questions about line graphs of graphs. For instance, a hypergraph whose edges all have size k is called k-uniform. (A 2-uniform hypergraph is a graph). In hypergraph theory, it is often natural to require that hypergraphs be k-uniform. Every graph is the line graph of some hypergraph, but, given a fixed edge size k, not every graph is a line graph of some k-uniform hypergraph. A main problem is to characterize those that are, for each k ≥ 3. A hypergraph is linear if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, not only of some hypergraph, but of some linear hypergraph. (en) Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа. Вопросы о рёберных графах гиперграфов часто являются обобщениями вопросов о рёберных графах обычных графов. Например, гиперграф, все рёбра которого имеют размер k, называется k-униформным' (2-униформный гиперграф — это обычный граф). В теории гиперграфов часто естественно требовать k-униформность. Любой обычный граф является рёберным графом некоего гиперграфа, но если зафиксировать размер ребра k (число точек множества, принадлежащего ребру), не всякий граф является рёберным графом какого-либо k-униформного графа. Основная задача — описать рёберные графы для каждого . Гиперграф называется линейным, если любая пара гиперрёбер имеет в пересечении максимум одну вершину. Любой граф является рёберным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Repeated_diamond_graph.svg?width=300 |
| dbo:wikiPageExternalLink | https://hal.inria.fr/hal-02360671/file/21-BHS77-L%28H%29.pdf |
| dbo:wikiPageID | 16181442 (xsd:integer) |
| dbo:wikiPageLength | 10071 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1095244061 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_families dbr:Intersection dbr:Generalization dbr:Graph_(discrete_mathematics) dbr:Line_graph dbr:Clique_(graph_theory) dbr:Complement_graph dbr:Finite_set dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Graphs_and_Combinatorics dbr:Intersection_graph dbr:Hypergraph dbr:Diamond_graph dbc:Hypergraphs dbr:Set_(mathematics) dbr:Vertex_(graph_theory) dbr:Forbidden_induced_subgraph dbr:Nova_Science_Publishers,_Inc. dbr:File:Repeated_diamond_graph.svg |
| dbp:last | Naik (en) Rao (en) Shrikhande (en) Singhi (en) |
| dbp:nb | yes (en) |
| dbp:txt | yes (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Harvnb dbt:Harvs |
| dbp:year | 1980 (xsd:integer) 1982 (xsd:integer) |
| dct:subject | dbc:Graph_families dbc:Hypergraphs |
| 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 | In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraph H, denoted L(H), is the graph whose vertex set is the set of the hyperedges of H, with two vertices adjacent in L(H) when their corresponding hyperedges have a nonempty intersection in H. In other words, L(H) is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph. A hypergraph is linear if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, not only of some hypergraph, but of some linear hypergraph. (en) Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа. Гиперграф называется линейным, если любая пара гиперрёбер имеет в пересечении максимум одну вершину. Любой граф является рёберным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа. (ru) |
| rdfs:label | Line graph of a hypergraph (en) Рёберный граф гиперграфа (ru) |
| owl:sameAs | freebase:Line graph of a hypergraph yago-res:Line graph of a hypergraph wikidata:Line graph of a hypergraph dbpedia-ru:Line graph of a hypergraph https://global.dbpedia.org/id/4qP4L |
| prov:wasDerivedFrom | wikipedia-en:Line_graph_of_a_hypergraph?oldid=1095244061&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Repeated_diamond_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Line_graph_of_a_hypergraph |
| is dbo:wikiPageRedirects of | dbr:Intersection_(Line)_Graphs_of_hypergraphs dbr:Line_graphs_of_hypergraphs dbr:Linear_Hypergraphs |
| is dbo:wikiPageWikiLink of | dbr:Hypertree dbr:Pathwidth dbr:Line_graph dbr:Abstract_simplicial_complex dbr:Erdős–Faber–Lovász_conjecture dbr:Forbidden_graph_characterization dbr:Hall-type_theorems_for_hypergraphs dbr:Hypergraph dbr:Width_of_a_hypergraph dbr:Intersection_(Line)_Graphs_of_hypergraphs dbr:Line_graphs_of_hypergraphs dbr:Linear_Hypergraphs |
| is foaf:primaryTopic of | wikipedia-en:Line_graph_of_a_hypergraph |
