Grafo llindar

Archiu:Threshold graph.svg

Un eixemple de grafo llindar.

En teoria de grafos, un grafo llindar (millor conegut en anglés com threshold graph) és un grafo que pot ser construït des d'un únic vèrtiç aplicant repetidament qualsevol de les següents dos operacions:

1. Adició d'un vèrtiç aïllat al grafo, és dir, d'un vèrtiç en grau 0.
2. Adició d'un vèrtiç dominant al grafo, és dir, d'un vèrtiç que està conectat a tots els demés vèrtiços.

Per eixemple, el grafo de la figura és un grafo llindar. Pot construir-se començant en el vèrtiç 1, i després afegint vèrtiços negres com a vèrtiços aïllats i vèrtiços rojos com a vèrtiços dominants, seguint l'orde en que estan enumerats.

Història

Estos grafos varen ser per primera volta introduïts per Václav Chvátal i Peter Hammer en el seu artícul de 1977. Un capítul complet sobre grafos llindars apareix en el llibre de Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs. La referència més completa en el tema és el llibre de Mahadev i Peled, Threshold Graphs and Related Topics.

Definicions alternatives

Una definició equivalent pot donar-se utilisant una funció llindar: un grafo és un threshold graph si existix un número real S i per a cada vétice v existix un pes w(v) para dit vèrtiç, tal que per a qualssevol dos vèrtiços v, o, (o,v) és una aresta si i solament si $w(u)+w(v)\ge S$.

A partir de la primera definició, es pot derivar una manera alternativa de descriure estos grafos per mig de strings o cadenes de caràcters. ε és sempre el primer caràcter de la cadena, i representa el primer vèrtiç del grafo. Cada caràcter subsecuente és o be una a, que denota l'adició d'un vèrtiç aïllat, o be una d, que denota l'adició d'un vèrtiç dominant. Aixina per eixemple, la cadena εuuj representa un grafo estrela en tres fulls, mentres que εuj és un camí de tres vèrtiços. El grafo de la primera figura pot representar-se com εuuujuuj.

En teoria de jocs cooperatius, un grafo llindar pot representar-se com un joc de majoria ponderada (o weighted game), a on cada vèrtiç del grafo representa un jugador, i si una aresta conecta dos vèrtiços i, j, llavors tant el conjunt {i, j} com cada u de les seues superconjuntos és una coalició guanyadora. Per esta raó, a estos grafos també se'ls sol cridar grafos en pesos (en anglés, weighted graphs).

Vore també

• Joc de majoria ponderada

Bibliografia

• . 2.ª edició, Annals of Discrete Mathematics, 57, Elsevier, 2004.