Hypergraph (original) (raw)
Hypergraf je pojem z teorie grafů. Jedná se o zobecnění pojmu graf. Rozdíl je v tom, že hrany hypergrafu (hyperhrany) mohou spojovat libovolný počet vrcholů, zatímco u grafu spojují hrany vždy dva vrcholy.
| Property | Value |
|---|---|
| dbo:abstract | En matemàtiques, i més concretament en teoria de grafs, un hipergraf és una generalització d'un graf en la qual les arestes poden connectar un nombre qualsevol de vèrtexs. Formalment, un hipergraf és un parell de conjunts , on és el conjunt d'elements anomenat nodes o vèrtexs i és un conjunt de subconjunts no-buits de anomenats hiperarestes o simplement arestes. Per tant, és un subconjunt de , on és el conjunt de les parts de . Mentre que les arestes d'un graf són parells de vèrtexs, les hiperarestes són conjunts arbitraris de vèrtexs, i per tant poden contenir un nombre arbitrari de vèrtexs. Tanmateix, sovint és interessant estudiar hipergrafs on totes les hiperarestes tenen la mateixa cardinalitat; un hipergraf k-uniforme és un hipergraf on totes les hiperarestes tenen grandària k (en altres paraules, un tal hipergraf és una col·lecció de conjunts, on cadascun representa una hiperaresta que connecta k vèrtexs). Així, un hipergraf 2-uniforme és un graf, un hipergraf 3-regular és una col·lecció de triplets no ordenats, i així successivament. Un hipergraf també es coneix com a sistema de conjunts o una escollits del conjunt universal X. La diferència entre un sistema de conjunts i un hipergraf és una qüestió encara ni tancada. La teoria d'hipergrafs tendeix a tractar qüestions simulars a les de la teoria de grafs, com la o la coloració, mentre que la teoria de sistemes de conjunts acostuma a tractar aspectes no relacionats amb la teoria de grafs, com a la teoria de Sperner. Existeixen diferents definicions per als hipergrafs; de vegades les arestes han de ser no buides, i de vegades es permeten arestes múltiples, que connecten el mateix conjunt de vèrtexs. Els hipergrafs es poden veure com a . En particular, existeix un "graf d'incidència" o "" corresponent a cada hipergraf; recíprocament, la majoria de grafs bipartits, però no qualsevol, es poden interpretar com a grafs d'incidència d'hipergrafs. Els hipergrafs tenen altres noms. En geometria computacional, un hipergraf es pot conèixer com a espai de rangs i les hiperarestes s'anomenen rangs. En teoria de jocs cooperatius, els hipergrafs es coneixen com a jocs simples (jocs de votació); aquesta noció s'aplica en la resolució de problemes de . Alguns autors es refereixen a les hiperarestes com a hiperenllaços o connectors. Alguns tipus especials d'hipergrafs inclouen, a part dels k-uniformes, els clutters, on cap aresta apareix com a subconjunt de cap altra aresta; i els , que contenen tots els subconjunts de cada aresta. La col·lecció dels hipergrafs és una categoria amb homomorfismes d'hipergrafs com a morfismes. (ca) Hypergraf je pojem z teorie grafů. Jedná se o zobecnění pojmu graf. Rozdíl je v tom, že hrany hypergrafu (hyperhrany) mohou spojovat libovolný počet vrcholů, zatímco u grafu spojují hrany vždy dva vrcholy. (cs) في الرياضيات، المخطط الزائدي أو الرسم الزائدي (بالإنجليزية: Hypergraph) هو تعميم لمفهوم والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، الرسم الزائدي هو الزوج المرتب حيث هي مجموعة من العناصر التي تسمى رؤوس، والمجموعة هي مجموعة غير خاليه جزئيه من . عناصر المجموعة تسمى أضلاع زائديه أو أضلاع. بالتالي هي مجموعة غير خاليه من مجموعة القوه . حجم مجموعة الرؤوس يسمى رتبة الرسم الزائدي بينما حجم مجموعة الاضلاع يسمى حجم الرسم الزائدي. في حين أن أضلاع الرسم البياني يحتوي على عنصرين فقط من مجموعة الرؤوس، الأضلاع الزائدية هي مجموعات مختارة من الرؤوس، ومن الممكن أن تحتوي على أي عدد من الرؤوس. لكن الغالب يرغب بدراسة الرسوم الزائديه التي كل أضلاعها تحتوي على نفس العدد من الرؤوس. الرسم الزائدي ذو أضلاع موحدة السعة (k-uniform hypergraph) هو الرسم الزائدي الذي كل ضلع زائدي به من الرؤوس، أو بمعنى آخر هو الرسم الزائدي الذي أضلاعه الزائدية هي مجموعات بها من الرؤوس. فبالتالي، الرسم الزائدي ذو اضلاع سعتها 2 هو الرسم البياني المعروف، والرسم الزائدي ذو الاضلاع الموحدة بسعة 3 هو مجموعة من المجموعات الثلاثية، أي بها 3 عناصر. الرسم الزائدي يسمى أيضاً بنظام المجموعة أو عائلة من المجموعات والمستوحاة من مجموعة شاملة. الرسومات الزائدية يمكن اعتبارها كهياكل الوقوع (incidence structures). وبصورة خاصة، يوجد مخطط وقوع ثنائي التجزئة (incidence graph" or Levi graph ) مقابل كل رسم زائدي. بالمقابل، ليس كل الرسومات البيانية الثنائية التجزئة يمكن اعتبارها كرسومات وقوع لرسومات زائدية. المخططات الزائدية لها مسميات عديدة. ففي الهندسة الحاسوبية يسمى المخطط الزائدي في بعض الاحيان بـ range space وبالتالي أضلاعه الزائدية تسمى ranges. تسمى الرسوم الزائديه في نظرية اللعب التعاوني بالألعاب البسيطة وينطبق نفس المسمى لحل المشاكل في نظرية الإختيار الإجتماعي. تسمى الأضلاع الزائدية في بعض الدراسات بالروابط الزائدية (hyperlinks) أو موصلات (connectors). يوجد أنواع خاصة من الرسومات الزائدية والمصنفه حسب سعة الأضلاع الزائديه بها. فمثلا الرسم الزائدي من السعة كما وضح أعلاه. ورسم زائدي اخر يسمى clutters والذي به كل ضلع زائدي ليس محتوى بأي ضلع زائدي آخر بنفس الرسم الزائدي. بالمقابل، الرسومات الزائديه التي تحتوي على كل المجموعات الجزئية من أي ضلع زائدي بها تسمى بـ abstract simplicial complexes. (ar) En matematiko, hipergrafeo estas aro , kie estas aro de elementoj (nomataj verticoj) kaj estas aro de subaroj de (nomataj eĝoj aŭ, pli precize, ). Hipergrafeo do estas ĝeneraligo de ordinara grafeo, kie eĝoj povas ligi pli ol du verticojn. Tiel hipereĝo estas ĝeneraligo de eĝo al ajna kvanto de la enhavataj verticoj. Se ĉiu hipereĝo konsistas el elementoj, la hipergrafeo nomiĝas -unuforma, aŭ simple -grafeo. Ordinara grafeo do estas 2-unuforma hipergrafeo aŭ 2-grafeo. (eo) En matemáticas y ciencias de la computación, un hipergrafo es una generalización de un grafo, cuyas aristas aquí se llaman hiperaristas, y pueden relacionar a cualquier cantidad de vértices, en lugar de solo un máximo de dos como en el caso de los grafos. Así, un grafo es una clase particular de hipergrafos, en que cada hiperarista tiene a lo más dos vértices. (es) In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph is a pair where is a set of elements called nodes or vertices, and is a set of non-empty subsets of called hyperedges or edges. Therefore, is a subset of , where is the power set of . The size of the vertex set is called the order of the hypergraph, and the size of edges set is the size of the hypergraph. A directed hypergraph differs in that its hyperedges are not sets, but ordered pairs of subsets of , with each pair's first and second entries constituting the tail and head of the hyperedge respectively. While graph edges connect only 2 nodes, hyperedges connect an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting k nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. An undirected hypergraph is also called a set system or a family of sets drawn from the universal set. Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs. Hypergraphs have many other names. In computational geometry, an undirected hypergraph may sometimes be called a range space and then the hyperedges are called ranges.In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory. In some literature edges are referred to as hyperlinks or connectors. The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms. (en) Les hypergraphes sont des objets mathématiques généralisant la notion de graphe.Ils ont été nommés ainsi par Claude Berge dans les années 1960. Les hypergraphes généralisent la notion de graphe non orienté dans le sens où les arêtes ne relient plus un ou deux sommets, mais un nombre quelconque de sommets (compris entre un et le nombre de sommets de l’hypergraphe). Certains théorèmes de la théorie des graphes se généralisent naturellement aux hypergraphes, par exemple le théorème de Ramsey. Les hypergraphes sont manipulés dans tous les domaines où on utilise la théorie des graphes : résolution de problèmes de satisfaction de contraintes, traitement d’images, optimisation d’architectures réseaux, modélisation, etc. (fr) 하이퍼그래프(Hypergraph)는 수학적으로는 복잡하게 연결된 도형과 숫자를 꼭짓점과 선으로 단순화 시켜서 연결한 일종의 일반화된 변환 그래프이다. 전자공학에서는 게이트와 넷으로 구성된 디지털 회로를 꼭짓점과 원, 점선 등으로 알기 쉽게 표현하고 이것으로 회로를 분석에 사용한다. (ko) In matematica, un ipergrafo è un grafo in cui un arco può essere collegato a un qualunque numero di vertici. Formalmente, un ipergrafo è una coppia dove è un insieme di elementi chiamati nodi oppure vertici, e è un insieme formato da sottoinsiemi non vuoti chiamati oppure archi. Pertanto, è un sottoinsieme di , dove è l'insieme potenza di . Mentre in un grafo gli archi sono formati da una coppia di nodi, gli iperarchi sono insieme di nodi di grandezza arbitraria, e pertanto possono contenere qualsivoglia numero intero positivo di nodi. Tuttavia, è spesso desiderabile il caso di ipergrafi dove tutti gli iperarchi hanno la stessa cardinalità; un ipergrafo k-uniforme è un ipergrafo in cui tutti gli iperarchi hanno grandezza k. In altre parole, un ipergrafo di questo genere è una collezione di insiemi, in cui ogni insieme è un iperarco connesso a k nodi. Ne segue che un ipergrafo 2-uniforme è un grafo, un ipergrafo 3-uniforme è una collezione di triple non ordinata, e così via. Un ipergrafo è anche chiamato insieme sistema o anche presa da insieme universo X. La differenza tra un insieme sistema e un ipergrafo è una domanda che spesso sorge spontanea. La teoria degli ipergrafi tende ad occuparsi di questioni simili a quelle della teoria dei grafi, quali connettività e colorabilità, mentre la teoria degli insiemi tende a occuparsi di domande non inerenti alla teoria dei grafi, quali la . Esistono diverse definizioni: a volte gli archi non devono essere vuoti e a volte archi multipli, con lo stesso insieme di nodi, sono ammessi. Gli ipergrafi possono essere visti come . In particolare, esiste un "grafo incidente" biparito o "" corrispondente a ogni ipergrafo, al contrario, la maggior parte dei grafi bipartiti, ma non tutti, possono essere considerati come grafi di incidenza, o ipergrafi. Gli ipergrafi hanno tanti altri nomi. In geometria computazionale, un ipergrafo può a volte essere definito come range space, e gli iperarchi vengono chiamati ranges.Nella teoria dei , gli ipergrafi vengono anche chiamati giochi semplici (voting games); questa nozione viene applicata per risolvere problemi in ambito della teoria della scelta sociale. In alcuni articoli, gli archi vengono chiamati anche iperlink o connettori. Tra i casi particolari di vi sono: i grafi k-uniformi, come precedentemente discusso; i , dove nessun arco appare come sottoinsieme di un altro arco; e i , che contiene tutti i sottoinsiemi di ogni arco. La collezione degli ipergrafi è una categoria, avente gli omomorfismi di ipergrafi come morfismi. (it) ハイパーグラフ（英: Hypergraph）とは、数学におけるグラフを一般化（拡張）したもので、エッジ（枝）が任意個数のノード（頂点）を連結できる。形式的には という対で表され、 はノードあるいは頂点と呼ばれる要素の集合、 はハイパーエッジ（hyperedge）と呼ばれる の空集合でない部分集合の集合である。したがって、 は の部分集合である。ただし、 は の冪集合を表す。通常のグラフのエッジは2つのノードの対で表されるが、ハイパーエッジは任意のノードの集合で表され、任意個のノードを含む。 グラフとは異なり、ハイパーグラフは紙上に図示するのが困難である。そのため、グラフ理論のような図解をされることは少なく、集合論の用語で表される傾向がある。 (ja) Een hypergraaf is een veralgemeende vorm van een graaf. In een "gewone" graaf verbindt een kant twee knopen; maar in een hypergraaf kan een hyperkant een willekeurig aantal knopen omvatten, gaande van 1 tot het aantal knopen in de graaf. Een hypergraaf kan men beschouwen als een verzameling van deelverzamelingen van een gegeven basisverzameling. Formeel wordt een hypergraaf gedefinieerd als het paar H = (X, E), waarin X de verzameling van knopen is en E de verzameling van (hyper)kanten; elke hyperkant is een niet-lege deelverzameling van X. De problemen die in de grafentheorie optreden worden ook bestudeerd in hypergrafen, zoals kleuring, kantenbedekking en knopenbedekking, koppelingen, de verdeling van een graaf in cliques, het vinden van een Hamiltonpad of Hamiltoncircuit, enzovoort. (nl) Hipergraf – rozszerzenie pojęcia grafu. Jego krawędzie, nazywane hiperkrawędziami, mogą być incydentne do dowolnej liczby wierzchołków. Pojęcie hipergrafu pojawiło się w drugiej połowie ubiegłego stulecia. W 1973 roku francuski matematyk opublikował monografię „Grafy i hipergrafy”, w której sformalizował oraz ujednolicił podstawowe definicje dotyczące teorii hipergrafów. (pl) En hypergraf är, inom grafteori, en generalisering av en graf, vars bågar kan binda samman ett godtyckligt antal noder. (sv) Em teoria dos grafos, um hipergrafo é uma generalização de um grafo, com suas arestas ligando quaisquer quantidades positivas de vértices. (pt) Гіпергра́ф — узагальнення графу, в якому ребром називається не пара вершин графу, а довільна підмножина вершин графу. Математично, гіперграф являє собою пару , де — непорожня множина об'єктів деякої природи, які називають вершинами гіперграфу, — сімейство непорожніх підмножин множини , які називають ребрами гіперграфу. (uk) Гипергра́ф — обобщение графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества множества вершин. С математической точки зрения, гиперграф представляет собой пару , где — непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а — семейство непустых (необязательно различных) подмножеств множества , называемых рёбрами гиперграфа. Гиперграфы применяются, в частности, при моделировании электрических цепей. Трансверсалью гиперграфа является множество , содержащее непустое пересечение с каждым ребром. Такая трансверсаль будет минимальной, если никакое её подмножество само не является трансверсалью гиперграфа. (ru) 在数学中，超图（Hypergraph）是一种广义上的图，它的一条边可以连接任意数量的顶点。形式上，超图是一个集合组，其中是一个有限集合，该集合的元素被称为节点或顶点，是的非空子集的集合，被称为超边或连接。因此，是的一个子集，其中是的幂集。 尽管图的边各有一对节点，而超边是节点的任意集合，因而能包含任意数量的节点。然而，通常的研究更倾向于每个超边连接的节点数相同的超图：k-均匀超图（每个超边都连接了k个节点）。因此，2-均匀超图就是图，3-均匀超图就是三元组的集合，依此类推。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Hypergraph-wikipedia.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.aviz.fr/paohvis https://books.google.com/books%3Fid=1Jt7CwAAQBAJ&pg=PP3 https://books.google.com/books%3Fid=IvVIAQAACAAJ https://books.google.com/books%3Fid=Qr8jDwAAQBAJ https://books.google.com/books%3Fid=jEyfse-EKf8C https://books.google.com/books%3Fid=lb5DAAAAQBAJ&pg=PP1 |
| dbo:wikiPageID | 232535 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Graph_(Graphentheorie) |
| dbo:wikiPageLength | 42875 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1118352564 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_set dbr:Preorder dbr:Multigraph dbr:Homomorphism dbr:Permutation dbr:Cycle_(graph_theory) dbr:Vertex_cover_in_hypergraphs dbr:Incidence_matrix dbr:Index_set dbr:Induced_subgraph dbr:Levi_graph dbr:Connected_graph dbr:Matching_in_hypergraphs dbr:Mathematics dbr:Neighbourhood_(graph_theory) dbr:Claude_Berge dbr:Graph_(discrete_mathematics) dbr:Morphism dbr:NP-complete dbr:Confluence_(abstract_rewriting) dbr:Cooperative_game_theory dbr:Theorem dbr:Apache_Spark dbr:Linear_time dbr:Machine_learning dbr:Steiner_tree_problem dbr:Combinatorial_design dbr:Computational_geometry dbr:Computer_science dbr:Horn-satisfiability dbr:Kruskal–Katona_theorem dbr:Matroid dbr:Automorphism dbr:Transitive_closure dbr:Transpose dbr:Database_schema dbr:Database_theory dbr:Line_graph_of_a_hypergraph dbr:Graph_partitioning dbr:Spectral_graph_theory dbr:Abstract_simplicial_complex dbr:Adjacency_matrix dbr:Erdős–Ko–Rado_theorem dbr:First-order_logic dbr:Balanced_hypergraph dbr:Partially_ordered_set dbr:Partition_of_a_set dbr:Directed_graph dbr:Family_of_sets dbr:Graph_drawing dbr:Graph_partition dbr:Graph_theory dbr:Isomorphism dbr:Social_choice_theory dbr:Regularization_(mathematics) dbr:Group_(mathematics) dbr:Hall-type_theorems_for_hypergraphs dbr:Involution_(mathematics) dbr:Bachman_diagram dbr:Term_(logic) dbc:Families_of_sets dbr:Chordal_graph dbr:Bijection dbr:Bioinformatics dbr:Bipartite_graph dbr:Bipartite_hypergraph dbr:Term_algebra dbr:Directed_acyclic_graph dbr:Automorphism_group dbr:BF-graph dbc:Hypergraphs dbr:Planar_graph dbr:Connected_component_(graph_theory) dbr:Greedoid dbr:If_and_only_if dbr:Incidence_(geometry) dbr:Incidence_structure dbr:Category_(mathematics) dbr:Ramsey's_theorem dbr:Recommender_system dbr:Semi-supervised_learning dbr:Venn_diagram dbr:Vertex_(graph_theory) dbr:Universal_set dbr:Factor_graph dbr:Image_retrieval dbr:Forest_(graph_theory) dbr:Money_laundering dbr:Property_B dbr:Partial_order dbr:P_system dbr:Sparse_matrix–vector_multiplication dbr:Ronald_Fagin dbr:Spectral_clustering dbr:Axiom_of_foundation dbr:PTIME dbr:Guarded_fragment dbr:Hyperedges dbr:Hypergraph_grammar dbr:Incidence_graph dbr:Simple_closed_curve dbr:Ear_(graph_theory) dbr:File:CircuitoDosMallas.png dbr:File:Directed_hypergraph_example.svg dbr:File:Hypergraph-wikipedia.svg dbr:File:PAOH_hypergraph_representation.png dbr:File:Venn's_four_ellipse_construction.svg |
| dbp:id | p/h048470 (en) |
| dbp:title | Hypergraph (en) hypergraph (en) |
| dbp:urlname | hypergraph (en) |
| dbp:wikiPageUsesTemplate | dbt:Springer dbt:Authority_control dbt:Cite_book dbt:Colend dbt:Commons_category dbt:Reflist dbt:Rp dbt:Short_description dbt:Unreferenced_section dbt:Visible_anchor dbt:Incidence_structures dbt:Cols dbt:Graph_representations dbt:PlanetMath_attribution |
| dcterms:subject | dbc:Families_of_sets dbc:Hypergraphs |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | Hypergraf je pojem z teorie grafů. Jedná se o zobecnění pojmu graf. Rozdíl je v tom, že hrany hypergrafu (hyperhrany) mohou spojovat libovolný počet vrcholů, zatímco u grafu spojují hrany vždy dva vrcholy. (cs) En matematiko, hipergrafeo estas aro , kie estas aro de elementoj (nomataj verticoj) kaj estas aro de subaroj de (nomataj eĝoj aŭ, pli precize, ). Hipergrafeo do estas ĝeneraligo de ordinara grafeo, kie eĝoj povas ligi pli ol du verticojn. Tiel hipereĝo estas ĝeneraligo de eĝo al ajna kvanto de la enhavataj verticoj. Se ĉiu hipereĝo konsistas el elementoj, la hipergrafeo nomiĝas -unuforma, aŭ simple -grafeo. Ordinara grafeo do estas 2-unuforma hipergrafeo aŭ 2-grafeo. (eo) En matemáticas y ciencias de la computación, un hipergrafo es una generalización de un grafo, cuyas aristas aquí se llaman hiperaristas, y pueden relacionar a cualquier cantidad de vértices, en lugar de solo un máximo de dos como en el caso de los grafos. Así, un grafo es una clase particular de hipergrafos, en que cada hiperarista tiene a lo más dos vértices. (es) 하이퍼그래프(Hypergraph)는 수학적으로는 복잡하게 연결된 도형과 숫자를 꼭짓점과 선으로 단순화 시켜서 연결한 일종의 일반화된 변환 그래프이다. 전자공학에서는 게이트와 넷으로 구성된 디지털 회로를 꼭짓점과 원, 점선 등으로 알기 쉽게 표현하고 이것으로 회로를 분석에 사용한다. (ko) ハイパーグラフ（英: Hypergraph）とは、数学におけるグラフを一般化（拡張）したもので、エッジ（枝）が任意個数のノード（頂点）を連結できる。形式的には という対で表され、 はノードあるいは頂点と呼ばれる要素の集合、 はハイパーエッジ（hyperedge）と呼ばれる の空集合でない部分集合の集合である。したがって、 は の部分集合である。ただし、 は の冪集合を表す。通常のグラフのエッジは2つのノードの対で表されるが、ハイパーエッジは任意のノードの集合で表され、任意個のノードを含む。 グラフとは異なり、ハイパーグラフは紙上に図示するのが困難である。そのため、グラフ理論のような図解をされることは少なく、集合論の用語で表される傾向がある。 (ja) Hipergraf – rozszerzenie pojęcia grafu. Jego krawędzie, nazywane hiperkrawędziami, mogą być incydentne do dowolnej liczby wierzchołków. Pojęcie hipergrafu pojawiło się w drugiej połowie ubiegłego stulecia. W 1973 roku francuski matematyk opublikował monografię „Grafy i hipergrafy”, w której sformalizował oraz ujednolicił podstawowe definicje dotyczące teorii hipergrafów. (pl) En hypergraf är, inom grafteori, en generalisering av en graf, vars bågar kan binda samman ett godtyckligt antal noder. (sv) Em teoria dos grafos, um hipergrafo é uma generalização de um grafo, com suas arestas ligando quaisquer quantidades positivas de vértices. (pt) Гіпергра́ф — узагальнення графу, в якому ребром називається не пара вершин графу, а довільна підмножина вершин графу. Математично, гіперграф являє собою пару , де — непорожня множина об'єктів деякої природи, які називають вершинами гіперграфу, — сімейство непорожніх підмножин множини , які називають ребрами гіперграфу. (uk) 在数学中，超图（Hypergraph）是一种广义上的图，它的一条边可以连接任意数量的顶点。形式上，超图是一个集合组，其中是一个有限集合，该集合的元素被称为节点或顶点，是的非空子集的集合，被称为超边或连接。因此，是的一个子集，其中是的幂集。 尽管图的边各有一对节点，而超边是节点的任意集合，因而能包含任意数量的节点。然而，通常的研究更倾向于每个超边连接的节点数相同的超图：k-均匀超图（每个超边都连接了k个节点）。因此，2-均匀超图就是图，3-均匀超图就是三元组的集合，依此类推。 (zh) في الرياضيات، المخطط الزائدي أو الرسم الزائدي (بالإنجليزية: Hypergraph) هو تعميم لمفهوم والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، الرسم الزائدي هو الزوج المرتب حيث هي مجموعة من العناصر التي تسمى رؤوس، والمجموعة هي مجموعة غير خاليه جزئيه من . عناصر المجموعة تسمى أضلاع زائديه أو أضلاع. بالتالي هي مجموعة غير خاليه من مجموعة القوه . حجم مجموعة الرؤوس يسمى رتبة الرسم الزائدي بينما حجم مجموعة الاضلاع يسمى حجم الرسم الزائدي. (ar) En matemàtiques, i més concretament en teoria de grafs, un hipergraf és una generalització d'un graf en la qual les arestes poden connectar un nombre qualsevol de vèrtexs. Formalment, un hipergraf és un parell de conjunts , on és el conjunt d'elements anomenat nodes o vèrtexs i és un conjunt de subconjunts no-buits de anomenats hiperarestes o simplement arestes. Per tant, és un subconjunt de , on és el conjunt de les parts de . La col·lecció dels hipergrafs és una categoria amb homomorfismes d'hipergrafs com a morfismes. (ca) In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph is a pair where is a set of elements called nodes or vertices, and is a set of non-empty subsets of called hyperedges or edges. Therefore, is a subset of , where is the power set of . The size of the vertex set is called the order of the hypergraph, and the size of edges set is the size of the hypergraph. (en) Les hypergraphes sont des objets mathématiques généralisant la notion de graphe.Ils ont été nommés ainsi par Claude Berge dans les années 1960. Les hypergraphes généralisent la notion de graphe non orienté dans le sens où les arêtes ne relient plus un ou deux sommets, mais un nombre quelconque de sommets (compris entre un et le nombre de sommets de l’hypergraphe). Certains théorèmes de la théorie des graphes se généralisent naturellement aux hypergraphes, par exemple le théorème de Ramsey. (fr) In matematica, un ipergrafo è un grafo in cui un arco può essere collegato a un qualunque numero di vertici. Formalmente, un ipergrafo è una coppia dove è un insieme di elementi chiamati nodi oppure vertici, e è un insieme formato da sottoinsiemi non vuoti chiamati oppure archi. Pertanto, è un sottoinsieme di , dove è l'insieme potenza di . Esistono diverse definizioni: a volte gli archi non devono essere vuoti e a volte archi multipli, con lo stesso insieme di nodi, sono ammessi. La collezione degli ipergrafi è una categoria, avente gli omomorfismi di ipergrafi come morfismi. (it) Een hypergraaf is een veralgemeende vorm van een graaf. In een "gewone" graaf verbindt een kant twee knopen; maar in een hypergraaf kan een hyperkant een willekeurig aantal knopen omvatten, gaande van 1 tot het aantal knopen in de graaf. Een hypergraaf kan men beschouwen als een verzameling van deelverzamelingen van een gegeven basisverzameling. Formeel wordt een hypergraaf gedefinieerd als het paar H = (X, E), waarin X de verzameling van knopen is en E de verzameling van (hyper)kanten; elke hyperkant is een niet-lege deelverzameling van X. (nl) Гипергра́ф — обобщение графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества множества вершин. С математической точки зрения, гиперграф представляет собой пару , где — непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а — семейство непустых (необязательно различных) подмножеств множества , называемых рёбрами гиперграфа. Гиперграфы применяются, в частности, при моделировании электрических цепей. (ru) |
| rdfs:label | رسم زائدي (ar) Hipergraf (ca) Hypergraf (cs) Hypergraph (de) Υπεργράφημα (el) Hipergrafeo (eo) Hipergrafo (es) Hypergraph (en) Hypergraphe (fr) Ipergrafo (it) 하이퍼그래프 (ko) ハイパーグラフ (ja) Hypergraaf (nl) Hipergraf (pl) Hipergrafo (pt) Гиперграф (ru) Hypergraf (sv) Гіперграф (uk) 超图 (zh) |
| owl:sameAs | freebase:Hypergraph yago-res:Hypergraph http://d-nb.info/gnd/4161063-5 wikidata:Hypergraph dbpedia-ar:Hypergraph dbpedia-ca:Hypergraph dbpedia-cs:Hypergraph dbpedia-de:Hypergraph dbpedia-el:Hypergraph dbpedia-eo:Hypergraph dbpedia-es:Hypergraph dbpedia-fa:Hypergraph dbpedia-fr:Hypergraph dbpedia-he:Hypergraph dbpedia-hu:Hypergraph http://hy.dbpedia.org/resource/Հիպերգրաֆ dbpedia-it:Hypergraph dbpedia-ja:Hypergraph dbpedia-ko:Hypergraph dbpedia-nl:Hypergraph dbpedia-pl:Hypergraph dbpedia-pt:Hypergraph dbpedia-ru:Hypergraph dbpedia-sh:Hypergraph dbpedia-sl:Hypergraph dbpedia-sr:Hypergraph dbpedia-sv:Hypergraph http://ta.dbpedia.org/resource/மீகோட்டுரு dbpedia-uk:Hypergraph dbpedia-vi:Hypergraph dbpedia-zh:Hypergraph https://global.dbpedia.org/id/4zH2N |
| prov:wasDerivedFrom | wikipedia-en:Hypergraph?oldid=1118352564&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Venn's_four_ellipse_construction.svg wiki-commons:Special:FilePath/CircuitoDosMallas.png wiki-commons:Special:FilePath/Directed_hypergraph_example.svg wiki-commons:Special:FilePath/Hypergraph-wikipedia.svg wiki-commons:Special:FilePath/PAOH_hypergraph_representation.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Hypergraph |
| is dbo:wikiPageRedirects of | dbr:Host_graph dbr:Primal_graph_(hypergraphs) dbr:Dual_hypergraph dbr:Gaifman_graph dbr:Directed_hypergraph dbr:Hyper-graph dbr:Hypergraph_(mathematics) dbr:Hypergraph_acyclicity dbr:Hypergraphs dbr:Alpha-acyclic |
| is dbo:wikiPageWikiLink of | dbr:Entity–attribute–value_model dbr:List_of_data_structures dbr:Multigraph dbr:Polygon_mesh dbr:Olog dbr:Partial_linear_space dbr:Quantum_contextuality dbr:Binary_relation dbr:Dessin_d'enfant dbr:András_Hajnal dbr:Hypertree dbr:Betweenness dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Perfect_matching_in_high-degree_hypergraphs dbr:Reo_Coordination_Language dbr:Richard_Rado dbr:D-interval_hypergraph dbr:Vertex_cover dbr:Vertex_cover_in_hypergraphs dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:Degree_(graph_theory) dbr:Ε-net_(computational_geometry) dbr:Double_pushout_graph_rewriting dbr:Incidence_geometry dbr:Incidence_matrix dbr:Index_of_combinatorics_articles dbr:Levi_graph dbr:Positional_game dbr:Not-all-equal_3-satisfiability dbr:Configuration_(geometry) dbr:Matching_in_hypergraphs dbr:Mathematics dbr:Matroid_parity_problem dbr:Triangle_mesh dbr:Claude_Berge dbr:Giorgio_Ausiello dbr:Glossary_of_computer_graphics dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_removal_lemma dbr:Conflict-free_coloring dbr:Conjunctive_query dbr:Constraint_graph dbr:Constraint_satisfaction_problem dbr:Container_method dbr:Cooperative_game_theory dbr:Erdős_on_Graphs dbr:Erdős–Pósa_theorem dbr:Erdős–Stone_theorem dbr:LOGCFL dbr:Andy_Liu dbr:Line_graph dbr:Chordal_bipartite_graph dbr:Stephen_Wolfram dbr:Clique_complex dbr:Clique_percolation_method dbr:Combinatorial_design dbr:Community_structure dbr:Helly_family dbr:Kruskal–Katona_theorem dbr:Zsolt_Baranyai dbr:Tic-tac-toe dbr:Mathias_Schacht dbr:Host_graph dbr:800_(number) dbr:Timothy_Gowers dbr:TypeDB dbr:Václav_Chvátal dbr:Dually_chordal_graph dbr:GXL dbr:Hedgehog_(hypergraph) dbr:József_Beck dbr:Line_graph_of_a_hypergraph dbr:Abstract_simplicial_complex dbr:3-dimensional_matching dbr:Erdős–Faber–Lovász_conjecture dbr:Erdős–Ko–Rado_theorem dbr:Exact_cover dbr:Finitary_relation dbr:Forbidden_graph_characterization dbr:Balanced_hypergraph dbr:Baranyai's_theorem dbr:Discrepancy_of_hypergraphs dbr:Family_of_sets dbr:Forbidden_subgraph_problem dbr:Gordan's_lemma dbr:GraphML dbr:Graph_factorization dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Graph_partition dbr:Graph_rewriting dbr:Graph_theory dbr:Primal_graph_(hypergraphs) dbr:Reconstruction_conjecture dbr:Szemerédi_regularity_lemma dbr:Hall-type_theorems_for_hypergraphs dbr:Heilbronn_triangle_problem dbr:JUNG dbr:Jack_Edmonds dbr:Hypergraph_regularity_method dbr:Hypergraph_removal_lemma dbr:Power_graph_analysis dbr:Khanindra_Chandra_Chowdhury dbr:Bipartite_graph dbr:Bipartite_hypergraph dbr:Blocking_set dbr:Collaboration_graph dbr:Holographic_algorithm dbr:Homological_connectivity dbr:School_timetable dbr:Transversal_(combinatorics) dbr:Width_of_a_hypergraph dbr:Dominique_de_Caen dbr:BF-graph dbr:Sperner's_lemma dbr:Fiduccia–Mattheyses_algorithm dbr:Frequency_partition_of_a_graph dbr:Tic-tac-toe_variants dbr:Incidence_structure dbr:Independence_system dbr:Mihalis_Yannakakis dbr:Rainbow_matching dbr:Ramsey's_theorem dbr:Hypograph dbr:Penny_Haxell dbr:Schedule dbr:Volume_mesh dbr:Topic_map dbr:Extremal_Problems_For_Finite_Sets dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Property_B dbr:Range_space dbr:Flag_algebra dbr:Multiplicative_weight_update_method dbr:Packing_in_a_hypergraph dbr:P_system dbr:Slicing_the_Truth dbr:Topology_(electrical_circuits) dbr:Symmetric_hypergraph_theorem dbr:Ryser's_conjecture dbr:Turán_number dbr:Sparsity_matroid dbr:Truncated_projective_plane dbr:Susan_Morey dbr:Sperner_family dbr:Dual_hypergraph dbr:Gaifman_graph dbr:Directed_hypergraph dbr:Hyper-graph dbr:Hypergraph_(mathematics) dbr:Hypergraph_acyclicity dbr:Hypergraphs dbr:Alpha-acyclic |
| is gold:hypernym of | dbr:BF-graph |
| is foaf:primaryTopic of | wikipedia-en:Hypergraph |
