Matroide bicircular

En la materia matemática de teoría de matroides , el matroide bicircular de un grafo G es el matroide B ( G ) cuyos puntos son las aristas de G y cuyos conjuntos independientes son los conjuntos de aristas de pseudobosques de G , es decir, los conjuntos de aristas en los que cada componente conexo contiene como máximo un ciclo .

El matroide bicircular fue introducido por Simões-Pereira (1972) y explorado más a fondo por Matthews (1977) y otros. Es un caso especial del matroide de marco de un grafo sesgado .

Los circuitos, o conjuntos dependientes mínimos, de este matroide son los grafos bicirculares (o bicicletas , pero ese término tiene otros significados en la teoría de grafos); estos son grafos conexos cuyo rango de circuito es exactamente dos.

Hay tres tipos distintos de gráfico bicircular:

• El gráfico theta consta de tres caminos que unen los mismos dos vértices pero no se intersecan entre sí.
• El gráfico en forma de ocho (o esposas apretadas) consta de dos ciclos que tienen un solo vértice común.
• La esposas sueltas (o barra) consta de dos ciclos disjuntos y un camino de conexión mínimo.

Todas estas definiciones se aplican a los multigrafos , es decir, permiten múltiples aristas (aristas que comparten los mismos puntos finales) y bucles (aristas cuyos dos puntos finales son el mismo vértice).

Los conjuntos cerrados (planos) del matroide bicircular de un grafo G pueden describirse como los bosques F de G tales que en el subgrafo inducido de V ( G ) − V ( F ) , cada componente conexo tiene un ciclo. Dado que los planos de un matroide forman una red geométrica cuando se ordenan parcialmente por inclusión de conjuntos, estos bosques de G también forman una red geométrica. En el ordenamiento parcial para esta red, que F ₁ ≤ F ₂ si

• cada árbol componente de F ₁ está contenido en cada árbol de F ₂ o es disjunto en sus vértices , y
• cada vértice de F ₂ es un vértice de F ₁ .

Para dar el ejemplo más interesante, supongamos que G  ^o es G con un bucle añadido a cada vértice. Entonces, los planos de B ( G  ^o ) son todos los bosques de G , ya sean generadores o no generadores. Por lo tanto, todos los bosques de un grafo G forman una red geométrica, la red de bosques de G (Zaslavsky 1982).

Los matroides bicirculares pueden caracterizarse como los matroides transversales que surgen de una familia de conjuntos en la que cada elemento del conjunto pertenece a dos conjuntos como máximo. Es decir, los conjuntos independientes del matroide son los subconjuntos de elementos que pueden utilizarse para formar un sistema de representantes distintos para algunos o todos los conjuntos. En esta descripción, los elementos corresponden a las aristas de un grafo, y hay un conjunto por vértice, siendo el conjunto de aristas el que tiene ese vértice como punto final.

A diferencia de los matroides transversales en general, los matroides bicirculares forman una clase menor-cerrada ; es decir, cualquier submatroide o contracción de un matroide bicircular es también un matroide bicircular, como se puede ver a partir de su descripción en términos de grafos sesgados (Zaslavsky 1991). Aquí hay una descripción de la eliminación y contracción de una arista en términos del grafo subyacente: Para eliminar una arista del matroide, quítela del grafo. La regla para la contracción depende de qué tipo de arista sea. Para contraer un enlace (un no bucle) en el matroide, contráigalo en el grafo de la manera habitual. Para contraer un bucle e en el vértice v , elimine e y v pero no las otras aristas incidentes con v; en cambio, cada arista incidente con v y otro vértice w se convierte en un bucle en w . Cualquier otro bucle de grafo en v se convierte en bucles de matroide; para describir esto correctamente en términos del grafo, se necesitan medias aristas y aristas sueltas; vea menores de grafos sesgados .

El polinomio característico del matroide bicircular B ( G  ^o ) expresa de forma sencilla el número de bosques de expansión (bosques que contienen todos los vértices de G ) de cada tamaño en G . La fórmula es

${\displaystyle p_{B(G)}(\lambda):=\sum _ {k=0}^{n}(-1)^{k}f_{k}(\lambda -1)^{nk} ,}$

donde f _k es igual al número de bosques que abarcan k aristas en G . Véase Zaslavsky (1982).

Las matroides bicirculares, como todas las demás matroides transversales, pueden representarse mediante vectores sobre cualquier cuerpo infinito . Sin embargo, a diferencia de las matroides gráficas , no son regulares : no pueden representarse mediante vectores sobre un cuerpo finito arbitrario . La cuestión de los campos sobre los que una matroide bicircular tiene una representación vectorial conduce al problema, en gran medida no resuelto, de encontrar los campos sobre los que un grafo tiene ganancias multiplicativas . Véase Zaslavsky (2007).

• Matthews, Laurence R. (1977), "Matroides bicirculares", Quarterly Journal of Mathematics , Segunda serie, 28 (110): 213–227, doi :10.1093/qmath/28.2.213, MR  0505702.
• Simões-Pereira, JMS (1972), "Sobre subgrafos como células matroides", Mathematische Zeitschrift , 127 : 315–322, doi :10.1007/BF01111390, MR  0317973.
• Zaslavsky, Thomas (1982), "Geometría bicircular y la red de bosques de un grafo", Quarterly Journal of Mathematics , Segunda serie, 33 (132): 493–511, doi :10.1093/qmath/33.4.493, MR  0679818.
• Zaslavsky, Thomas (1991), "Grafos sesgados. II. Los tres matroides", Journal of Combinatorial Theory , Serie B, 51 (1): 46–72, doi : 10.1016/0095-8956(91)90005-5 , MR  1088626.
• Zaslavsky, Thomas (2007), "Gráficos sesgados. VII. Contrapesos y antivoltajes", Journal of Combinatorial Theory , Serie B, 97 (6): 1019–1040, doi : 10.1016/j.jctb.2007.03.001 , MR  2354716.