Diferencia entre revisiones de «Estructura de incidencia»

Ejemplo 2: puntos y círculoscircunferencias (centro),<br />

En [[matemáticas]], una '''estructura de incidencia''' es un sistema abstracto que consta de dos tipos de objetos y una única relación entre estos tipos de objetos. Considérense los [[Punto (geometría)|puntos]] y las [[recta]]s de un [[Plano (geometría)|plano]] como los dos tipos de objetos, e ignórense todas las propiedades de esta geometría, excepto el criterio de [[Relación binaria|relación]], es decir, establecer qué puntos están en qué rectas para todos los puntos y rectas definidos. Lo que queda es la estructura de incidencia delen un plano euclídeo.

Las estructuras de incidencia se consideran con mayor frecuencia en el contexto geométrico, donde se trabaja sobre planos (como el [[plano afín]], el [[plano proyectivo]] o el [[plano de Möbius]]), pero el concepto es muy amplio y no se limitafija aexclusivamente en las configuraciones geométricas. Incluso en un entorno geométrico, las estructuras de incidencia no se limitan solo a puntos y rectas; y se pueden utilizar objetos de dimensiones superiores ([[Bidimensional|planos]], [[Geometría del espacio|sólidos]], espacios {{mvar|n}}-dimensionales, o [[superficie cónica|superficies cónicas]]). El estudio de estructuras finitas a veces se denomina [[geometría finita]].<ref>{{harvnb|Colbourn|Dinitz|2007|page=702}}</ref>

Una '''estructura de incidencia''' es una tripleta ({{math|''P'', ''L'', ''I''}}) donde {{mvar|P}} es un conjunto cuyos elementos se llaman ''puntos'', {{mvar|L}} es un conjunto distinto cuyos elementos se llaman ''rectaslíneas'' y {{math|''I'' ⊆ ''P'' × ''L''}} es la [[Relación binaria|relación]] de [[Incidencia (geometría)|incidencia]]. Los elementos de {{mvar|I}} se llaman '''banderas'''. Si ({{math|''p'', ''l''}}) está en {{mvar|I}}, entonces se puede decir que el punto {{mvar|p}} "se encuentra en" la rectalínea {{mvar|l}} o que la rectalínea {{mvar|l}} "pasa por" el punto {{mvar|p}}. Una terminología más "simétrica", para reflejar la naturaleza [[Simetría en matemáticas|simétrica]] de esta relación, es que "{{mvar|p}} es ''incidente'' con {{mvar|l}}" o que "{{mvar|l}} es ''incidente'' con {{mvar|p}}" y se utiliza la notación {{math|''p'' I ''l''}} con el mismo significado que {{math|(''p'', ''l'') ∈ ''I''}}.<ref name=Demb1>{{harvnb|Dembowski|1968|pages=1–2}}</ref>

Una estructura de incidencia es ''uniforme'' si cada rectalínea incide con el mismo número de puntos. Cada uno de estos ejemplos, excepto el segundo, es uniforme (con tres puntos por rectalínea).

Cualquier [[Grafo|grafo]] (que no tiene por qué ser [[Grafo|simple]]; se permiten [[Bucle (teoría de grafos)|bucles]] y [[aristas múltiples]]) es una estructura de incidencia uniforme con dos puntos por rectalínea. Para estos ejemplos, los vértices del grafo forman el conjunto de puntos, los vínculos del grafo forman el conjunto de rectaslíneas, e incidencia significa que un vértice es un punto final de un vínculo.

Las estructuras de incidencia rara vez se estudian en toda su generalidad, y es típico estudiarcentrarse en aquellas que satisfacen algunos axiomas adicionales. Por ejemplo, un ''[[espacio lineal parcial]]'' es una estructura de incidencia que satisface:

# Dos puntos distintos cualesquiera inciden como máximo con una rectalínea común, y

# Cada rectalínea incide con al menos dos puntos.

Si el primer axioma anterior se reemplaza por ella condición más fuerte:

Un ejemplo más especializado es una {{mvar|k}}-'''red''', una estructura de incidencia en la que las rectaslíneas se clasifican en {{mvar|k}} '''clases paralelas''', de modo que dos rectaslíneas en la misma clase paralela no tienen puntos comunes, pero dos rectaslíneas en diferentes clases tienen exactamente un punto común, y cada punto pertenece exactamente a una rectalínea de cada clase paralela. Un ejemplo de una {{mvar|k}}-red es el conjunto de puntos de un [[plano afín]] junto con {{mvar|k}} clases de rectas afines paralelas.

Si se intercambia el papel de "puntos" y "rectaslíneas" en

[[FileArchivo:Fano plane with nimber labels.svg|thumb|right|Siete puntos son los elementos de siete líneas en el [[plano de Fano]]]]

Cada [[hipergrafo]] o [[sistema de conjuntos]] se puede considerar como una estructura de incidencia en la que el [[conjunto universal]] desempeña el papel de "puntos", la [[familia de conjuntos]] correspondiente desempeña el papel de "rectaslíneas" y la relación de incidencia es la [[Elemento de un conjunto|pertenencia a un conjunto]] "{{math|∈}}". Por el contrario, cada estructura de incidencia se puede ver como un hipergrafo identificando las rectaslíneas con los conjuntos de puntos que inciden en ellas.

Un diseño de bloque (en general) es un conjunto {{mvar|X}} junto con una [[Familia de conjuntos|familia {{mvar|F}} de subconjuntos]] de {{mvar|X}} (se permiten subconjuntos repetidos). Normalmente se requiere un diseño de bloque para satisfacer condiciones de regularidad numérica. Como estructura de incidencia, {{mvar|X}} es el conjunto de puntos y {{mvar|F}} es el conjunto de rectaslíneas, generalmente llamados ''bloques'' en este contexto (los bloques repetidos deben tener nombres distintos, por lo que {{mvar|F}} es en realidad un conjunto y no un conjunto múltiple). Si todos los subconjuntos en {{mvar|F}} tienen el mismo tamaño, el diseño del bloque se llama "uniforme". Si cada elemento de {{mvar|X}} aparece en el mismo número de subconjuntos, se dice que el diseño del bloque es "regular". El dual de un diseño uniforme es un diseño regular y viceversa.

Considérese el diseño de bloque/hipergrafíahipergrafo dado por

En el etiquetado dado, las rectaslíneas son precisamente los subconjuntos de los puntos que constan de tres puntos cuyas etiquetas suman cero usando ''[[nimber]]''. Alternativamente, cada número, cuando se escribe en el [[Sistemasistema binario|binario]], se puede identificar con un vector distinto de cero de longitud tres sobre el [[GF(2)|campo binario]]. Tres vectores que generan un [[Subespacio vectorial|subespacio]] forman una rectalínea; lo que en este caso equivale a que su suma vectorial sea el vector cero.

La '''matriz de incidencia''' de una estructura de incidencia (finita) es una [[matriz booleana]] que tiene sus filas indexadas por los puntos {{mvar|{p_i} }} y las columnas indexadas por las rectaslíneas {{math|{''l_j''} }} donde la entrada {{mvar|ij}}-ésima es 1 si es {{math|''p_i'' I ''l_j''}} y 0 en caso contrario.{{efn|La otra convención de indexar las filas por líneas y las columnas por puntos también se usa ampliamente.}} Una matriz de incidencia no está determinada de forma única, ya que depende del orden arbitrario de los puntos y las rectaslíneas.<ref name=Beth17>{{harvnb|Beth|Jungnickel|Lenz|1986|page=17}}</ref>

Una estructura de incidencia es autodual si existe un ordenamiento de los puntos y rectasde las líneas de modo que la matriz de incidencia construida con ese ordenamiento sea una [[matriz simétrica]].

Con las etiquetas como se muestra en el ejemplo número 1 anterior y con los puntos ordenadosen el orden {{math|''A'', ''B'', ''C'', ''D'', ''G'', ''F'', ''E''}} y las rectaslíneas en el ordenadasorden {{math|''l'', ''p'', ''n'', ''s'', ''r'', ''m'', ''q''}}, el plano de Fano tiene la matriz de incidencia:

Una figura de incidencia (es decir, una representación de una estructura de incidencia) se construye representando los puntos mediante puntos en un plano y teniendo algún medio visual para unir los puntos para que correspondan a rectaslíneas.<ref name=Beth17 /> Los puntos se pueden colocar de cualquier manera, no hay restricciones en cuanto a distancias entre puntos ni relaciones entre puntos. En una estructura de incidencia no existe el concepto de que un punto esté entre otros dos puntos; el orden de los puntos en una rectalínea no está definido. Compárese esto con la [[geometría ordenada]], quedonde sí tieneexiste unael nociónconcepto de intermediaciónposición intermedia. Se pueden hacer las mismas afirmaciones sobre las representaciones de las rectaslíneas. En particular, no es necesario representar las rectasrepresentalas mediante "segmentos de recta recta" (véanse los ejemplos 1, 3 y 4 anteriores). Al igual que con la representación pictórica de [[grafo]]s, el cruce de dos "rectas"líneas en cualquier lugar que no sea un punto no tiene significado en términos de la estructura de incidencia; es solo un ''accidente'' de la representación. Estas figuras de incidencia pueden a veces parecerse a grafos, pero no lo son a menos que la estructura de incidencia reúna las propiedades de un grafo.

Las estructuras de incidencia se pueden modelar mediante puntos y curvas en un [[Plano (geometría)|plano]] con el significado geométrico habitual de incidencia. Algunas estructuras de incidencia admiten representación pormediante puntos y líneas rectas. Las estructuras que pueden serlo se denominan "factibles" o "realizables". Si no se menciona ningún espacio de contorno, se supone el plano euclídeo. El plano de Fano (ejemplo 1 anterior) no es factible, ya que necesita al menos una curva. La configuración de Möbius-Kantor (ejemplo 4 anterior) no es realizable en el plano euclídeo, pero sí en el [[plano complejo]].<ref>{{harvnb|Pisanski|Servatius|2013|page=222}}</ref> Por otra parte, los ejemplos 2 y 5 anteriores son realizables y las figuras de incidencia dadas lo demuestran. Steinitz (1894)<ref>E. Steinitz (1894), ''Über die Construction der Configurationen'' {{math|''n''₃}}, Dissertation, Breslau</ref> demostró que las {{nowrap|{{math|''n''₃}}-configuraciones}} (estructuras de incidencia con {{mvar|n}} puntos y {{mvar|n}} rectas, tres puntos por recta y tres rectas que pasan por cada punto) son realizables o requieren el uso de una sola rectalínea curva en sus representaciones.<ref>{{citation|first=Harald|last=Gropp|title=Configurations and their realizations|journal=Discrete Mathematics|year=1997|volume=174|pages=137–151|doi=10.1016/s0012-365x(96)00327-5}}</ref> El plano de Fano es el único ejemplo del tipo ({{math|7₃}}) y la configuración de Möbius-Kantor es la única del tipo ({{math|8₃}}).

[[ImageImagen:Fano plane-Levi graph.svg|thumb|[[Grafo de Heawood]] con etiquetas]]

Cada estructura de incidencia {{mvar|C}} corresponde a un [[grafo bipartito]] llamado [[grafo de Levi]] o grafo de incidencia de la estructura. Como cualquier grafo bipartito tiene dos colores, al grafo de Levi se le puede dar una [[Coloración de grafos|coloración de vértices]] en blanco y negro, donde los vértices negros corresponden a puntos y los vértices blancos corresponden a rectaslíneas de {{mvar|C}}. Los vínculos de este grafo corresponden a las banderas (pares de puntos/rectaslíneas incidentes) de la estructura de incidencia. El grafo de Levi original era el grafo de incidencia del [[cuadrángulo generalizado]] de orden dos (ejemplo 3 anterior),<ref>{{citation|last= Levi|first= F. W.|author-link= Friedrich Wilhelm Levi|location= Calcutta|mr= 0006834|publisher= University of Calcutta|title= Finite Geometrical Systems|year= 1942}}</ref> pero [[Harold Scott MacDonald Coxeter|Coxeter]]<ref>{{citation|first=H.S.M.|last=Coxeter|author-link=H.S.M. Coxeter|title=Self-dual configurations and regular graphs|journal=Bulletin of the American Mathematical Society|volume=56|year=1950|pages=413–455|doi=10.1090/s0002-9904-1950-09407-5}}</ref> ha ampliado el término para referirse a un grafo de incidencia de cualquier estructura de incidencia.<ref name=Pisanski158>{{harvnb|Pisanski|Servatius|2013|page=158}}</ref>

[[FileArchivo:Möbius–Kantor unit distance.svg|left|thumb|Grafo de Levi de la configuración de Möbius–Kantor (#4)]]

*[[Incidencia (geometría)|Incidencia]]