Definició
Si elimina un vèrtex d'un graf G (natural, mentre que l'eliminació del vèrtex associat amb totes les vores) després del número de sucursals augmentar connectivitat mapa, anomenat el vèrtex del punt de tall G (cut-vèrtex).
Punt de tall
La figura anterior, v3, v4 és el punt de tall.Teorema
1 de G si i només si hi ha dos diferents vèrtex v vèrtexs u i w, de manera que tot el (o, w) quan el camí a través de v, v és el punt de tall.
(2) un graf connex G té almenys dos vèrtexs no es tallen punts.
3 arbre a sol tots els vèrtexs són més grans que un punt de tall. [1]
|