Sa se demonstreze ca pentru orice arbore T, ck(T) = T .
Pentru orice graf simplu conex G=(V,E), notam cu ck(G) graful simplu obtinut astfel:ck(G) = (V,E∪{xy|x,y∈centr(G),x!=y}).
More Questions From This User See All
Show life that you have a thousand reasons to smile
© Copyright 2024 DOKU.TIPS - All rights reserved.
Demonstrarea se poate face prin tehnica reducerii la absurd.
Presupunem ca exista un arbore T care sa aiba proprietatea ck(T) ≠ T.
In acest caz, graful ck(T) are cel putin doua muchii E' care nu apartin lui T.
Deci, daca luam un varf v in E', trebuie sa existe cel putin doua muchii incidente lui v care sa nu apartina lui T.
Deci exista cel putin doua varfuri care aduc cicluri in T, ceea ce contrazice definitia unui arbore.
Prin urmare, pentru orice arbore T, ck(T) = T. 1:01 PM