Ipergrafo: differenze tra le versioni

Versione delle 12:30, 6 gen 2019

Versione delle 16:30, 14 feb 2019

Riga 1:

{{T|lingua=inglese|argomento=matematica|data=maggio 2018|commento = vi sono lacerti di frase non ancora tradotti}}

[[File:Hypergraph-wikipedia.svg|frame|destra|

Riga 12 ⟶ 11:

]]

In [[matematica]], un '''ipergrafo''' è un [[grafo]] in cui un arco può essere collegato a un qualunque numero di [[Vertice (teoria dei grafi)| vertici]]. Formalmente, un ipergrafo <math>H</math> è una coppia <math>H = (X,E)</math> dove <math>X</math> è un insieme di elementi chiamati ''nodi'' oppure ''vertici'', e <math>E</math> è un insieme formato da sottoinsiemi non vuoti <math>X</math> chiamati [[iperarchi]] oppure archi. Pertanto, <math>E</math> è un sottoinsieme di <math>\mathcal{P}(X) \setminus\{\emptyset\}</math>, dove <math>\mathcal{P}(X)</math> è l' [[insieme potenza]] di <math>X</math>.

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 [[famiglia di insiemi]] 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 [[Grafo #Connettività |connettività]] e [[graph coloring|colorability]], mentre la teoria degli insiemi tende ad occuparsi di domande di ambito non grafo-teorico, quali [[Sperner's theorem|Sperner theory]].

Esistono diverse definizioni; a volte gli archi non devono essere vuoti, e a volte archi multipli, con lo stesso insieme di noti, sono ammessi.

Riga 76 ⟶ 75:

:<math>\left(H^*\right)^* = H.</math>

Un [[grafo connesso]] ''G'' con lo stesso insieme vertice di un ipergrafo connesso ''H'' è un grafo ospite per ''H'' se ogni iperarco di ''H'' [[sottografo indotto| induce ]] a un sottografo connesso in ''G''. Per un ipergrafo disconnesso ''H'', ''G'' è un grafo ospite se esiste una funzione biettiva tra le [[Componente connessa (teoria dei grafi)|componenti connesse]] di ''G'' e di ''H'', tale che ogni componente connessa ''G<nowiki>'</nowiki>'' di ''G'' è un ospite del corrispondente ''H<nowiki>'</nowiki>''.

A ipergrafo bipartito se e solo se i suoi vertici possono essere divisi in due classi, ''U'' e ''V'', in modo tale che ogni iperarco di cardinalità almeno 2 contenga almeno un vertice da entrambe le classi.

Riga 113 ⟶ 112:

:<math>H \simeq G</math> se e solo se<math>H^* \simeq G^*</math>.

Quando gli archi di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ''ismomorfismo forte''. Si dice che <math>H</math> è fortemente isomorfo a <math>G</math> se la permutazione è l'identità. Scritto: <math>H \cong G</math>. Naturalmente un grafo fortemente isomorfo è anche un grafo isomorfio, ma non viceversa.

Quando i vertici di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ''equivalenza'', e anche di ''uguaglianza''. Si dice che <math>H</math> è equivalente a <math>G</math>, e si scrive <math>H\equiv G</math> se l'isomorfismo <math>\phi</math> ha

Riga 194 ⟶ 193:

== Altri progetti ==

{{Interprogetto}}

{{Portale|matematica}}

{{controllo di autorità}}

{{Portale|matematica}}

[[Categoria:Teoria dei grafi]]

[[de:Graph (Graphentheorie)#Hypergraph]]