b"\n_START_ARTICLE_\nIpergrafo\n_START_SECTION_\nModello di un grafo bipartito\n_START_PARAGRAPH_\nUn ipergrafo H pu\xc3\xb2 essere rappresentato da un grafo bipartito BG come segue: gli insiemi X e E sono le partizioni di BG, e (x\xe2\x82\x81,  e\xe2\x82\x81) sono connessi con un arco se e solo se il vertice x\xe2\x82\x81 \xc3\xa8 contenuto nell'arco e\xe2\x82\x81 in H. Contrariamente, ogni grafo bipartito con parti fissate e alcun nodo sconnesso nella seconda parte, rappresenta l'idea di ipergrafo appena descritta. Questo esempio di grafo bipartito viene anche chiamato grafo di incidenza.\n_START_SECTION_\nAciclicit\xc3\xa0\n_START_PARAGRAPH_\nIn contrasto con ordinari grafi sconnessi per i quali esiste una singola nozione naturale di cicli e grafi aciclici, esistono multiple definizioni non-equivalenti di aciclicit\xc3\xa0 per ipergrafi che \xc3\xa8 in contrasto con l'ordinaria aciclicit\xc3\xa0 dei grafi, nel caso particolare di grafi ordinari._NEWLINE_Una prima definizione di aciclicit\xc3\xa0 per ipergrafi viene data da Claude Berge: un ipergrafo \xc3\xa8 Berge-aciclico se il suo grafo di incidenza (il grafo bipartito sopra definito) \xc3\xa8 aciclico. Tale definizione \xc3\xa8 molto restrittiva: per esempio, se un ipergrafo ha una coppia  di vertici e alcune coppie  di iperarchi tali che  and , allora esso \xc3\xa8 Berge-ciclico. La Berge-cyclicit\xc3\xa0 pu\xc3\xb2 ovviamente essere indagata in tempo lineare esplorando un grafo di incidenza._NEWLINE_Possiamo utilizzare una definizione pi\xc3\xb9 debole di aciclicit\xc3\xa0 di ipergrafo, in seguito chiamata \xce\xb1-aciclicit\xc3\xa0. Tale nozione di aciclicit\xc3\xa0 \xc3\xa8 equivalente a quella di un ipergrafo conforme (ogni cricca del grafo originario \xc3\xa8 coperta da alcuni iperarchi) e avente grafo originario cordale; esso \xc3\xa8 anche equivalente alla riducibilit\xc3\xa0 di un grafo vuoto tramite GYO algorithm (anche noto come algoritmo di Graham), un processo iterativo confluente che rimuove gli iperarchi utilizzando una definizione generica di ears. Entrando nel dominio della teoria delle basi di dati, \xc3\xa8 noto che un schema di database gode di alcune desiderabili propriet\xc3\xa0 se l'ipergrafo sottostante \xc3\xa8 \xce\xb1-aciclico. Inoltre, \xce\xb1-aciclicit\xc3\xa0 \xc3\xa8 anche legata all'espressivit\xc3\xa0 del frammento custodito di logica del primo ordine._NEWLINE_Si pu\xc3\xb2 provare  in tempo lineare se un ipergrafo sia \xce\xb1-aciclico._NEWLINE_Bisogna per\xc3\xb2 far notareche l'\xce\xb1-aciclicit\xc3\xa0 ha la seguente propriet\xc3\xa0 contro intuitiva: aggiungere iperarchi a un ipergrafo \xce\xb1-ciclico pu\xc3\xb2 renderlo \xce\xb1-aciclico (per esempio, aggiungere un iperarco contenente tutti i vertici dell'ipergrafo lo render\xc3\xa0 sempre \xce\xb1-aciclico). Tale limite viene in parte motivato, Ronald Fagin defin\xc3\xac le nozioni pi\xc3\xb9 forti di \xce\xb2-aciclicit\xc3\xa0 e \xce\xb3-aciclicit\xc3\xa0. Possiamo definire la \xce\xb2-aciclicit\xc3\xa0 come il requisito affinch\xc3\xa9 tutti i sottoipergrafi di un ipergrafo siano \xce\xb1-aciclici, che \xc3\xa8 equivalente a una precedente definizione di Graham. La nozione di \xce\xb3-aciclicit\xc3\xa0 \xc3\xa8 una condizione pi\xc3\xb9 restrittiva, che \xc3\xa8 equivalente a diverse propriet\xc3\xa0 desiderabili di uno schema di una base di dati ed \xc3\xa8 legato ai diagrammi di Bachman. Sia \xce\xb2-aciclicit\xc3\xa0 che \xce\xb3-aciclicit\xc3\xa0 possono essere esplorate in tempo polinomiale._NEWLINE_Queste quattro nozioni di aciclicit\xc3\xa0 possono essere confrontate: la Berge-aciclicit\xc3\xa0 implica \xce\xb3-aciclicit\xc3\xa0 che a sua volta implica \xce\xb2-aciclicit\xc3\xa0 che implica \xce\xb1-aciclicit\xc3\xa0. Tuttavia nessuna delle precedenti implicazioni pu\xc3\xb2 essere invertita, e pertanto sono considerate acicliti\xc3\xa0 differenti.\n_START_SECTION_\nIpergrafi Simmetrici\n_START_PARAGRAPH_\nIl rango  di un hypergraph  \xc3\xa8 la cardinalit\xc3\xa0 massima che di un arco nell'ipergrafo. Se tutti gli archi hanno stessa cardinalit\xc3\xa0 k, l'ipergrafo viene detto uniforme o anche k-uniforme, o anche chiamato k-ipergrafo.  Un grafo si tratta di un ipergrafo 2-uniforme._NEWLINE_Il grado d(v) di un vertice v \xc3\xa8 il numero di archi in cui \xc3\xa8 contenuto. H \xc3\xa8 k-regolare se ogni vertice ha grado k._NEWLINE_Il duale di un ipergrafo uniforme \xc3\xa8 regolare, e viceversa_NEWLINE_Due vertici x e y di H sono chiamati simmetrici se esiste un automorfismo tale che .  Due archi  e  sono detti simmetrici se esiste un automorfismo tale che ._NEWLINE_Un ipergrafo \xc3\xa8 detto vertice-transitivo (o vertice-simmetrico) se tutti i suoi vertici sono simmetrici. Ne segue che un ipergrafo si dice arco-transitivo se tutti gli archi sono simmetrici. Se un ipergrafo \xc3\xa8 sia arco-simmetrico che vertice-simmetrico, allora l'ipergrafo si dice transitivo._NEWLINE_Data la dualit\xc3\xa0 di un ipergrafo, lo studio della arco-transitivit\xc3\xa0 \xc3\xa8 collegato allo studio della vertice-transitivit\xc3\xa0."