Revisión del 01:12 2 ago 2008 editar GermanX (discusión · contribs.) Autoverificados 24 580 ediciones m →‎Referencias: +cat ← Ir a diferencia anterior		Revisión del 04:39 26 sep 2008 editar deshacer Farisori (discusión · contribs.) Burócratas, Bibliotecarios 121 805 ediciones actualizo Ir a siguiente diferencia →
Línea 1: [[Image:Hypergraph.gif\|right\|frame\|Ejemplo de hipergrafo <math>H=\{e_1,e_2,e_3,e_4\}=\{\{v_1, v_2, v_3\},\{v_2,v_3\},\{v_3,v_5,v_6\},\{v_4\}\}</math>, definido sobre el conjunto base <math>A = \{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}</math>. Aquí ''H'' es ''propio'', tiene ''dominio parcial'', su ''cardinalidad'' es 4 y su ''tamaño'' 28.]] ~~[[Image:Hypergraph.gif\|right\|frame\|~~ En [[matemática]] y [[ciencias de la computación]], un '''hipergrafo''' es una generalización de un [[grafo]], cuyas [[arista (teoría de grafos)\|aristas]] aquí se llaman [[hiperarista]]s, y pueden relacionar a cualquier cantidad de [[vértice (teoría de grafos)\|vértices]]. ~~Ejemplo de Hipergrafo: <math>A = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math>,~~ ~~<math>H= \{e_1,e_2,e_3,e_4\}</math>~~ ~~<math>=\{\{v_1, v_2, v_3\}, \{v_2,v_3\},</math>~~ ~~<math>\{v_3,v_5,v_6\},\{v_4\}\}</math>.~~ ]] ~~Un '''hipergrafo'''~~Formalmente, dado un [[conjunto finito]] ~~<math>~~''A~~</math>,~~'' llamado ''conjunto base'', un hipergrafo ''H'' es una [[familia de conjuntos\|familia]] de [[subconjunto]]s de <math>A</math>; es decir, un subconjunto de <math>P(A)</math>, que es el [[conjunto potencia]] de <math>A</math>. Los elementos de un hipergrafo se llaman [[hiperarista]]s, las cuales a su vez son subconjuntos de <math>A</math>. La [[Número cardinal\|cardinalidad]] de un hipergrafo es su número de hiperaristas, y se denota ''\|H\|''. El '''tamaño''' o '''volumen''' de un hipergrafo, se define como ''\|A\|·\|H\|''. Un hipergrafo se puede ver además como un [[grafo]] generalizado ''(V,E)'', donde ''V=A'', y ''E'' es el conjunto de [[Arista (teoría de grafos)\|aristas]] (hiperaristas, en este contexto), las cuales pueden relacionar cualquier número de [[Vértice (Teoría de grafos)\|nodos]] (elementos del conjunto base). == Historia == Este término fue acuñado por el matemático francés [[Claude Berge]].<ref>''Graphs and Hypergraphs''. Dunod, París. 1970.</ref> Los hipergrafos se utilizan actualmente para representar problemas de [[lógica matemática\|lógica]], [[optimización (matemática)\|optimización]], [[teoría de juegos]], [[inteligencia artificial]], entre muchos otros. Este término fue acuñado por el matemático francés [[Claude Berge]] en 1970<ref>{{cita libro \| apellidos = Berge \| nombre = Claude \| enlaceautor = \| coautores = \| editorial = Monographies Universitaires de Mathématiques \| editor = \| otros = \| título = Graphes et hypergraphes \| edición = 37 \| fecha = \| año = 1970 \| mes = \| ubicación = [[Dunod]], [[París]] \| id = \| isbn = \| páginas = \| capítulo = \| URLcapítulo = \| cita = }}</ref>. Desde entonces, se ha desarrollado toda una teoría de hipergrafos, que aunque a veces trata conceptos y problemas similares a los de la [[teoría de grafos]], muchas veces se distancia de ésta última. Los hipergrafos se utilizan actualmente en distintas áreas, tales como la [[lógica matemática\|lógica]], la [[optimización (matemática)\|optimización]], [[teoría de juegos]], [[inteligencia artificial]], [[minería de datos]], indexación de [[bases de datos]], entre muchas otras. == Propiedades == * El número de hiperaristas de un hipergrafo <math>H</math> corresponde a la [[Número cardinal\|cardinalidad]] del hipergrafo, y se denota <math>\|H\|</math>. Además, el '''tamaño''' o '''volumen del hipergrafo''', está dado por ''\|A\|·\|H\|''. * Un hipergrafo es '''propio''', si no es vacío ni contiene la hiperarista vacía. * Un hipergrafo tiene '''dominio total''' si la unión de las hiperaristas es igual al conjunto ~~<math>~~''A~~</math>~~''; de lo contrario, se dice que tiene '''dominio parcial'''. ~~'''Ejemplo.''' Sea <math>A:=\{a,b,c\}</math>, entonces <math>H:=\{ \{a,b\},\{b,c\},\{c\} \}</math> es un hipergrafo propio, con dominio total, de tamaño 9 y con <math>\|H\|=3</math>.~~ == Estructura de hipergrafos == Una '''estructura de hipergrafos''' es un [[par ordenado]] ''G:=(H,K)'' de dos hipergrafos ~~<math>~~''H~~</math>~~'' y ~~<math>~~''K~~</math>~~'', bajo el mismo conjunto base. El '''tamaño''' o '''volumen''' de una estructura está dada por ''\|A\|·(\|H\|+\|K\|)''.▼ '''Ejemplo:''' Sea <math>A:=\{a,b,c\}</math>, entonces <math>G:=(H, K)</math>, con <math>H:=\{ \{a,b\},\{b,c\},\{c\} \}</math> y <math>K:=\{ \{a,c\},\{b,c\},\{a,b,c\} \}</math> es una estructura (de hipergrafos).▼ === Ejemplo === ▲El tamaño o volumen de una estructura está dada por ''\|A\|·(\|H\|+\|K\|)''. ▲~~'''Ejemplo:'''~~ Sea <math>A:=\{a,b,c\}</math>, entonces <math>G:=(H, K)</math>, con <math>H:=\{ \{a,b\},\{b,c\},\{c\} \}</math> y <math>K:=\{ \{a,c\},\{b,c\},\{a,b,c\} \}</math> es una estructura (de hipergrafos), de tamaño 18. == Referencias == {{listaref}} ~~<references/>~~ [[Categoría:Teoría de conjuntos]]

Diferencia entre revisiones de «Hipergrafo»