En matemáticas , un grafo sesgado es un grafo con una lista de círculos distinguidos (conjuntos de aristas de ciclos simples ), de modo que si dos círculos de la lista están contenidos en un grafo theta , entonces el tercer círculo del grafo theta también está en la lista. Un grafo sesgado es una generalización de los elementos combinatorios esenciales de un grafo de ganancia y, en particular, de un grafo con signo .
Formalmente, un grafo sesgado Ω es un par ( G , B ) donde B es una clase lineal de círculos; ésta, por definición, es una clase de círculos que satisface la propiedad del grafo theta mencionada anteriormente.
Un subgrafo o conjunto de aristas cuyos círculos están todos en B (y que no contiene medias aristas ) se llama equilibrado . Por ejemplo, un círculo que pertenece a B está equilibrado y uno que no pertenece a B está desequilibrado .
Los grafos sesgados son interesantes principalmente por sus matroides , pero también por su conexión con cuasigrupos multiarios . Véase más abajo.
Un grafo sesgado puede tener medias aristas (un punto final) y aristas sueltas (ningún punto final). Las aristas con dos puntos finales son de dos tipos: un enlace tiene dos puntos finales distintos, mientras que un bucle tiene dos puntos finales coincidentes.
Las clases lineales de círculos son un caso especial de subclases lineales de circuitos en un matroide .
Un menor de un grafo sesgado Ω = ( G , B ) es el resultado de cualquier secuencia de toma de subgrafos y contracción de conjuntos de aristas. Para los grafos sesgados, como para los grafos, basta con tomar un subgrafo (que puede ser el grafo entero) y luego contraer un conjunto de aristas (que puede ser el conjunto vacío).
Un subgrafo de Ω consiste en un subgrafo H del grafo subyacente G , con clase de círculo balanceado que consiste en aquellos círculos balanceados que están en H . La eliminación de un conjunto de aristas S , escrito Ω − S , es el subgrafo con todos los vértices y todas las aristas excepto las de S .
La contracción de Ω es relativamente complicada. Para contraer una arista e , el procedimiento depende del tipo de arista e que sea. Si e es un enlace, contráigalo en G . Un círculo C en la contracción G / e está equilibrado si C o es un círculo equilibrado de G . Si e es un bucle equilibrado o una arista suelta, simplemente se elimina. Si es un bucle desequilibrado o una media arista, se eliminan él y su vértice v ; cada otra arista con v como punto final pierde ese punto final, por lo que un enlace con v como un punto final se convierte en una media arista en su otro punto final, mientras que un bucle o media arista en v se convierte en una arista suelta.
En la contracción Ω/ S por un conjunto de aristas arbitrario S , el conjunto de aristas es E − S . (Dejamos G = ( V , E ).) El conjunto de vértices es la clase de conjuntos de vértices de componentes balanceadas del subgrafo ( V , S ) de Ω. Es decir, si ( V , S ) tiene componentes balanceadas con conjuntos de vértices V 1 , ..., V k , entonces Ω/ S tiene k vértices V 1 , ..., V k . Una arista e de Ω, no en S , se convierte en una arista de Ω/ S y cada punto final v i de e en Ω que pertenece a algún V i se convierte en el punto final V i de e en Ω/ S ; por lo tanto, un punto final de e que no está en una componente balanceada de ( V , S ) desaparece. Una arista con todos los puntos finales en componentes desbalanceadas de ( V , S ) se convierte en una arista suelta en la contracción. Una arista con un solo punto final en un componente equilibrado de ( V , S ) se convierte en una semiarista. Una arista con dos puntos finales que pertenecen a diferentes componentes equilibrados se convierte en un enlace, y una arista con dos puntos finales que pertenecen al mismo componente equilibrado se convierte en un bucle.
Hay dos tipos de matroide asociados con un gráfico sesgado, los cuales generalizan el matroide de ciclo de un gráfico (Zaslavsky, 1991).
El matroide de marco (a veces llamado matroide de polarización ) de un grafo polarizado, M (Ω), (Zaslavsky, 1989) tiene como conjunto base el conjunto de aristas E . Un conjunto de aristas es independiente si cada componente no contiene círculos o solo contiene un círculo, lo cual está desequilibrado. (En la teoría de matroides, una media arista actúa como un bucle desequilibrado y una arista suelta actúa como un bucle equilibrado). M (Ω) es un matroide de marco en el sentido abstracto, lo que significa que es un submatroide de un matroide en el que, para al menos una base, el conjunto de líneas generadas por pares de elementos de base cubre todo el matroide. A la inversa, cada matroide de marco abstracto es el matroide de marco de algún grafo polarizado.
Los circuitos del matroide se denominan circuitos de marco o circuitos de polarización . Hay cuatro tipos. Uno es un círculo equilibrado. Otros dos tipos son un par de círculos desequilibrados junto con un camino simple de conexión, de modo que los dos círculos son disjuntos (entonces, el camino de conexión tiene un extremo en común con cada círculo y es disjunto de ambos) o comparten solo un único vértice común (en este caso, el camino de conexión es ese único vértice). El cuarto tipo de circuito es un grafo theta en el que cada círculo está desequilibrado.
El rango de un conjunto de aristas S es n − b , donde n es el número de vértices de G y b es el número de componentes equilibrados de S , contando los vértices aislados como componentes equilibrados.
Los menores del matroide de marco concuerdan con los menores del gráfico sesgado; es decir, M (Ω− S ) = M (Ω)− S y M (Ω/ S ) = M (Ω)/ S .
Los matroides de marco generalizan las geometrías de Dowling asociadas con un grupo (Dowling, 1973). El matroide de marco de un 2 C n sesgado (ver Ejemplos, arriba) que no tiene dígones balanceados se llama remolino . Es importante en la teoría de la estructura de los matroides.
El matroide de sustentación extendido L 0 (Ω) tiene como conjunto base el conjunto E 0 , que es la unión de E con un punto extra e 0 . El matroide de sustentación L (Ω) es el matroide de sustentación extendido restringido a E . El punto extra actúa exactamente como un bucle desequilibrado o un medio borde, por lo que describimos solo el matroide de sustentación.
Un conjunto de aristas es independiente si no contiene ningún círculo o solo contiene un círculo, lo cual no está equilibrado.
Un circuito es un círculo equilibrado, un par de círculos no equilibrados que están disjuntos o tienen solo un vértice en común, o un gráfico theta cuyos círculos están todos desequilibrados.
El rango de un conjunto de aristas S es n − c + ε, donde c es el número de componentes de S , contando los vértices aislados, y ε es 0 si S está equilibrado y 1 si no lo está.
Los menores de los matroides de sustentación y sustentación extendida concuerdan en parte con los menores del grafo sesgado. Las eliminaciones concuerdan: L (Ω− S ) = L (Ω)− S . Las contracciones concuerdan solo para conjuntos de aristas balanceadas: M (Ω/ S ) = M (Ω)/ S si S está balanceado, pero no si está desbalanceado. Si S está desbalanceado, M (Ω/ S ) = M ( G )/ S = M ( G / S ) donde M de un grafo denota el matroide gráfico ordinario .
El matroide de sustentación de un 2 C n (ver ejemplos, arriba) que no tiene dígonos balanceados se llama pico . Los picos son bastante importantes en la teoría de la estructura del matroide.
Así como una expansión grupal de un grafo completo K n codifica el grupo (ver geometría de Dowling ), su análogo combinatorio que expande un ciclo simple de longitud n + 1 codifica un cuasigrupo n -ario (multiario) . Es posible demostrar teoremas sobre cuasigrupos multiarios por medio de grafos sesgados (Zaslavsky, ta)
