Vèrtiç (teoria de grafos)

Un grafo en 6 vèrtiços i 7 arestes.

En teoria de grafos, un vèrtiç o nodo és l'unitat fonamental de la que estan formats els grafos. Un grafo no dirigit està format per un conjunt de vèrtiços i un conjunt d'arestes (parells no ordenats de vèrtiços), mentres que un grafo dirigit està compost per un conjunt de vèrtiços i un conjunt de arcs (parells ordenats de vèrtiços). En este context, els vèrtiços són tractats com a objectes indivisibles i sense propietats, encara que puguen tindre una estructura adicional depenent de l'aplicació per la qual s'usa el grafo; per eixemple, una ret semàntica és un grafo en a on els vèrtiços representen conceptes o classes d'objectes.

Els dos vèrtiços que conformen una aresta es diuen punts finals ("endpoints", en anglés), i eixa aresta es diu que és incident als vèrtiços. Un vèrtiç w és adjacent a un atre vèrtiç v si el grafo conté una aresta (v,w) que els unix. La veïnat d'un vèrtiç v és un grafo induït del grafo, format per tots els vèrtiços adjacents a v.

Vèrtiços i graus

Artícul principal → Grau (teoria de grafos).

El grau d'un vèrtiç en un grafo és el número d'arestes incidents a ell. Un vèrtiç aïllat és un vèrtiç en grau zero; açò és, un vèrtiç que no és punt final de cap aresta. Un vèrtiç full és un vèrtiç en grau un. En un grafo dirigit, es pot distinguir entre grau d'eixida ("outdegree", número d'arestes que ixen del vèrtiç) i grau d'entrada ("indegree", número d'arestes que apleguen al vèrtiç); un vèrtiç font és un vèrtiç en grau d'entrada zero, mentres que un sumidero és un vèrtiç en grau d'eixida zero.

Conexions de vèrtiços

Un vèrtiç de tall és un vèrtiç que en remoure-ho desconecta al grafo restant. Un conjunt independent és un conjunt de vèrtiços tal que cap és adjacent a un atre, i una cobertura de vèrtiços és un conjunt de vèrtiços que inclou els punts finals de cada aresta en un grafo.

Referències

• Berge, Claude, Théorie dones graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, París 1958, viii+277 pp. (Edició anglesa, Wiley 1961; Methuen & Co, Nova York 1962; Rússia, Moscou 1961; Espanya, Mèxic 1962; Romania, Bucarest 1969; China, Shanghái 1963; Segona impressió de la primera edició anglesa de 1962. Dover, New York 2001)
• Chartrand, Gary, Introductory Graph Theory, Dover. ISBN 0-486-24775-9.
• Biggs, N.; Lloyd, E. & Wilson, R. Graph Theory, 1736-1936 Oxford University Press, 1986
• Harary, Frank, Graph Theory, Addison-Wesley, Reading, MA, 1969.
• Harary, Frank, i Palmer, Edgar M., Graphical Enumeration (1973), Academic Press, Nova York, NY.

Vore també

• Aresta
• Grafo
• Teoria de grafos