Feladat: 7.9.
Bizonyítsuk be a következőket:
a) Az eljárás végén kapott
G0
részgráf körmentes.
b) Az eljárás végén kapott
G0
részgráfnak ugyanannyi komponense van, mint magának a
G gráfnak.
c) Mi mondható az eljárás során a
T-ben levő élek számának és a komponensek számának az összegéről?
d) Ha
G pontszáma
n, komponenseinek száma
k, akkkor az eljárás végén
T-ben levő élek száma
n-k.
Megoldás: 7.9
a) nyilvánvaló, hiszen épp úgy válogattuk az éleket
T-be, hogy ne alkossanak kört.
b) Egyetlen részgráfnak sem lehet kevesebb komponense, mint az eredeti gráfnak, tehát az eljárás végén kapott
G0
feszítő részgráfnak sem. De több sem lehet. Tegyük fel ugyanis, hogy van egy
e él az eredeti
G gráfban, amely
G0
két komponensét köti össze. Ez azt jelentené, hogy
e végpontjai között nem fut
T-beli élekből álló út, mégsem választottuk ki. Ez azonban lehetetlen, hiszen amikor sorra került, éppen azért nem választottuk ki, mert már az aktuális
T-beli élekből álló út is volt a végpontjai között.
c) megválaszolásához szükségünk van a következő, nyilvánvaló megállapításokra. Az első esetben - amikor a soron következő él kört zár be a már
T-be kiválasztott élekkel, akkor
T változatlan marad, így a
T-ben levő élek által meghatározott komponensek is változatlanok maradnak.
Ellenkező esetben a sorra vett
ei
él két, a
Tr
-ben levő élek által meghatározott komponenst köt össze, azaz most a komponensek száma eggyel csökken, viszont
T éleinek száma eggyel nő. Ebből máris következik az a) állítás:
A
T-ben levő élek száma és a komponensek számának összege változatlan (a komponensek száma pontosan akkor csökken eggyel, amikor
T-be új élt teszünk). Minthogy kezdetben
T üres, s így minden csúcs egy-egy komponens, ezért kezdetben ez az összeg a csúcsok számával egyenlő.
d) egyszerű következménye c)-nek.