Egy elvágó pont (artikulációs pont) egy olyan csúcsa egy összefüggő gráfnak, amelynek elhagyásával a megmaradó részgráf már nem összefüggő (szétesik; egy csúcsot mindig csak a vele szomszédos élekkel együtt lehet elhagyni).
Nyilvánvaló, hogy ha egy gráfban van elsőfokú pont, akkor az nem elvágó pont. Az elsőfokú pont bármely favázban is elsőfokú lesz, tehát végpont lesz.
Megjegyzés: A pontok kerületi sorrend szerinti felsorolása a kerület egy elvágó pontjának (esetleges) kijelölését kívája. A kerület pontjainkat körszerűen helyezi el. Kiinduló csúcsot nekünk kell ``mesterségesen'' kijelölnünk.
(a) Tekintsünk egy 2 hosszúságú utat. Ahhoz, hogy egy reguláris példát kapjunk, válasszunk egy u elvágó pontot. (b) Létezik egy természetes bijekció az u -ból v -be menő, és a v -ből u -ba menő séták között.
41. feladat F M ...
 See also: Részgráf, Gráf, Összefüggő, Halmaz, Távolság
  
|
RSS
