Gráfico de umbral

Gráfico formado sumando vértices aislados o universales

Un ejemplo de gráfico de umbral.

En teoría de grafos , un gráfico de umbral es un gráfico que se puede construir a partir de un gráfico de un vértice mediante aplicaciones repetidas de las dos operaciones siguientes:

1. Adición de un único vértice aislado al gráfico.
2. Adición de un único vértice dominante al gráfico, es decir, un único vértice que está conectado a todos los demás vértices.

Por ejemplo, el gráfico de la figura es un gráfico de umbral. Se puede construir comenzando con un gráfico de un solo vértice (vértice 1) y luego agregando vértices negros como vértices aislados y vértices rojos como vértices dominantes, en el orden en que están numerados.

Los gráficos de umbral fueron introducidos por primera vez por Chvátal y Hammer (1977). En Golumbic (1980) aparece un capítulo sobre gráficos de umbral, y el libro Mahadev & Peled (1995) está dedicado a ellos.

Definiciones alternativas

Una definición equivalente es la siguiente: un gráfico es un gráfico de umbral si hay un número real y para cada vértice un peso de vértice real tal que para dos vértices cualesquiera , es una arista si y sólo si . ${\displaystyle S}$ ${\displaystyle v}$ ${\displaystyle w(v)}$ ${\displaystyle v,u}$ ${\displaystyle uv}$ ${\displaystyle w(u)+w(v)>S}$

Otra definición equivalente es esta: un gráfico es un gráfico de umbral si hay un número real y para cada vértice un peso de vértice real tal que para cualquier conjunto de vértices , es independiente si y sólo si ${\displaystyle T}$ ${\displaystyle v}$ ${\displaystyle a(v)}$ ${\displaystyle X\subseteq V}$ ${\displaystyle X}$ ${\displaystyle \sum _{v\in X}a(v)\leq T.}$

El nombre "gráfico de umbral" proviene de estas definiciones: S es el "umbral" de la propiedad de ser una arista, o equivalentemente, T es el umbral de ser independiente.

Los gráficos de umbral también tienen una caracterización de gráfico prohibido : un gráfico es un gráfico de umbral si y solo si ninguno de sus cuatro vértices forma un subgrafo inducido que sea un gráfico de ruta de tres bordes , un gráfico de ciclo de cuatro bordes o un gráfico de dos bordes. coincidente .

Descomposición

De la definición que utiliza la suma repetida de vértices, se puede derivar una forma alternativa de describir de forma única un gráfico de umbral, mediante una cadena de símbolos. es siempre el primer carácter de la cadena y representa el primer vértice del gráfico. Cada carácter subsiguiente es , que denota la adición de un vértice aislado (o vértice de unión ), o , que denota la adición de un vértice dominante (o vértice de unión ). Por ejemplo, la cadena representa un gráfico de estrella con tres hojas, mientras que representa un camino en tres vértices. La gráfica de la figura se puede representar como ${\displaystyle \epsilon }$ ${\displaystyle u}$ ${\displaystyle j}$ ${\displaystyle \epsilon uuj}$ ${\displaystyle \epsilon uj}$ ${\displaystyle \epsilon uuujuuj}$

Clases relacionadas de gráficos y reconocimiento.

Los gráficos de umbral son un caso especial de cografos , gráficos divididos y gráficos trivialmente perfectos . Un gráfico es un gráfico de umbral si y sólo si es a la vez un cografo y un gráfico dividido. Cada gráfico que es a la vez un gráfico trivialmente perfecto y el gráfico complementario de un gráfico trivialmente perfecto es un gráfico de umbral. Los gráficos de umbral también son un caso especial de los gráficos de intervalo . Todas estas relaciones pueden explicarse en términos de su caracterización mediante subgrafos inducidos prohibidos. Un cografo es un gráfico sin camino inducido en cuatro vértices, P ₄ , y un gráfico de umbral es un gráfico sin P ₄ , C ₄ ni 2K ₂ inducidos . C ₄ es un ciclo de cuatro vértices y 2K ₂ es su complemento, es decir, dos aristas disjuntas. Esto también explica por qué los gráficos de umbral están cerrados al aceptar complementos; el P ₄ es autocomplementario, por lo tanto, si un gráfico está libre de P ₄ -, C ₄ - y 2K _{2 -} , su complemento también lo es.

Heggernes y Kratsch (2007) demostraron que los gráficos de umbral se pueden reconocer en tiempo lineal; Si un gráfico no es un umbral, se generará una obstrucción (una de P ₄ , C ₄ o 2K _{2 ).}

Ver también

• Gráfico de indiferencia
• Gráfico serie-paralelo
• Hipergrafías de umbral ^[1]

Referencias

1. Reiterman, enero; Rödl, Vojtěch; Šiňajová, Edita; Tůma, Miroslav (1 de abril de 1985). "Hipergrafías de umbral". Matemáticas discretas . 54 (2): 193–200. doi : 10.1016/0012-365X(85)90080-9 . ISSN  0012-365X.

• Chvátal, Václav ; Hammer, Peter L. (1977), "Agregación de desigualdades en programación entera", en Hammer, PL; Johnson, EL; Korte, BH; et al. (eds.), Estudios de programación entera (Proc. Worksh. Bonn 1975) , Annals of Discrete Mathematics, vol. 1, Ámsterdam: Holanda Septentrional, págs. 145-162.
• Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y gráficos perfectos , Nueva York: Academic Press. 2ª edición, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
• Heggernes, Pinar ; Kratsch, Dieter (2007), "Algoritmos de reconocimiento de certificación de tiempo lineal y subgrafos inducidos prohibidos" (PDF) , Nordic Journal of Computing , 14 (1–2): 87–108 (2008), MR  2460558.
• Mahadev, NVR; Peled, Uri N. (1995), Gráficos de umbrales y temas relacionados , Elsevier.

enlaces externos

• Gráficos de umbrales, Sistema de Información sobre Clases de Gráficos y sus Inclusiones.