| 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)
|
| 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)
|
