Hispanopedia Wiki
Articulo de referencia

Matroide bicircular

El matroide bicircular de un grafo G. Cada conjunto independiente forma un pseudobosque , donde cada componente conexa contiene como máximo un ciclo . El único conjunto dependie...

Hispanopedia WikiContenido en espanolLectura gratuita
El matroide bicircular de un grafo G. Cada conjunto independiente forma un pseudobosque , donde cada componente conexa contiene como máximo un ciclo . El único conjunto dependiente en el matroide dado es el conjunto{1,2,3,4,5}{\displaystyle \{1,2,3,4,5\}}describiendo todo el grafo G , que forma un grafo theta .

En el tema matemático de la 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 los pseudobosques de G , es decir, los conjuntos de aristas en los que cada componente conexa contiene como máximo un ciclo .

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

Circuitos

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.

Existen tres tipos distintos de grafo bicircular:

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

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).

Pisos

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 conexa 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, F 1 ≤ F 2 si

  • cada árbol componente de F 1 está contenido en o es disjunto por vértices de cada árbol de F 2 , y
  • cada vértice de F 2 es un vértice de F 1 .

Para el ejemplo más interesante, sea G o un grafo G con un bucle añadido a cada vértice. Entonces, los planos de B ( G o ) son todos los bosques de G , 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 ) .

Como matroides transversales

Los matroides bicirculares se caracterizan como matroides transversales que surgen de una familia de conjuntos en la que cada elemento pertenece a un máximo de dos conjuntos. 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 existe un conjunto por vértice, el conjunto de aristas que tienen ese vértice como extremo.

menores

A diferencia de los matroides transversales en general, los matroides bicirculares forman una clase cerrada en menores ; es decir, cualquier submatroide o contracción de un matroide bicircular es también un matroide bicircular, como se puede ver en 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, se elimina del grafo. La regla para la contracción depende del tipo de arista que sea. Para contraer un enlace (un no bucle) en el matroide, se contrae en el grafo de la forma habitual. Para contraer un bucle e en el vértice v , se eliminan 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 del grafo en v se convierte en bucles del matroide ; para describir esto correctamente en términos del grafo se necesitan medias aristas y aristas sueltas; ver menores de grafos sesgados .

Polinomio característico

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

pagB(GRAMO)(λ):=∑k=0norte(−1)kFk(λ−1)norte−k,{\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) .

Representación vectorial

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

Referencias