En la 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:
- Adición de un único vértice aislado al gráfico.
- 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) . Un capítulo sobre gráficos de umbral aparece en Golumbic (1980) , 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 ventaja si y solo si.
Otra 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 cualquier conjunto de vértices , es independiente si y solo si
El nombre "gráfico de umbral" proviene de estas definiciones: S es el "umbral" para la propiedad de ser un borde, o equivalentemente T es el umbral para ser independiente.
Los gráficos de umbral también tienen una caracterización de gráfico prohibida : un gráfico es un gráfico de umbral si y solo si no cuatro de sus vértices forman un subgrafo inducido que es un gráfico de trayectoria de tres bordes , un gráfico de ciclo de cuatro bordes o un gráfico de dos bordes emparejamiento .
Descomposición
A partir de la definición que utiliza la suma repetida de vértices, se puede derivar una forma alternativa de describir unívocamente un gráfico de umbral, por medio de una cadena de símbolos. es siempre el primer carácter de la cadena y representa el primer vértice del gráfico. Cada personaje 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. El gráfico de la figura se puede representar como
Clases relacionadas de gráficos y reconocimiento
Gráficos umbral son un caso especial de cographs , gráficos de división y gráficos trivialmente perfectos . Un gráfico es un gráfico de umbral si y solo si es un gráfico cográfico 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 gráficos de intervalo . Todas estas relaciones pueden explicarse en términos de su caracterización mediante subgrafos inducidos prohibidos. Un cograph es un gráfico sin trayectoria inducida en cuatro vértices, P 4 , y un gráfico de umbral es un gráfico sin P 4 , C 4 ni 2K 2 inducidos . C 4 es un ciclo de cuatro vértices y 2K 2 es su complemento, es decir, dos aristas disjuntas. Esto también explica por qué se cierran los gráficos de umbrales para los complementos; el P 4 es autocomplementario, por lo tanto, si un gráfico es P 4 -, C 4 - y 2K 2 - libre, su complemento también lo es.
Heggernes y Kratsch (2007) demostraron que los gráficos de umbral pueden reconocerse en tiempo lineal; si un gráfico no es de umbral, se generará una obstrucción (una de P 4 , C 4 o 2K 2 ).
Ver también
Referencias
- Chvátal, Václav ; Hammer, Peter L. (1977), "Agregación de desigualdades en la programación de enteros", en Hammer, PL; Johnson, EL; Korte, BH; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975) , Annals of Discrete Mathematics, 1 , Amsterdam: North-Holland, págs. 145-162.
- Golumbic, Martin Charles (1980), Teoría de gráficos algorítmicos y gráficos perfectos , Nueva York: Academic Press. 2da edición, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
- Heggernes, Pinar ; Kratsch, Dieter (2007), "Algoritmos de reconocimiento de certificación en 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 umbral y temas relacionados , Elsevier.
enlaces externos
- Gráficos de umbral , Sistema de información sobre clases de gráficos y sus inclusiones.