Arbore cu doua orientari (folclor?)
Posted: Thu Jun 11, 2009 11:53 am
Fie G un arbore si consideram S, S' doua orientari ale sale.
Pentru un arbore orientat numim varf accesibil un varf care are numai grad interior sau numai grad exterior (adica nu sunt si muchii care intra si care ies din el).
Pentru un arbore orientat o mutare consta in a alege un varf accesibil si a schimba orientarea tuturor muchiilor ce il contin.
Demonstrati ca printr-un numar finit de mutari se poate ajunge de la orientarea S la orientarea S'.
Pentru un arbore orientat numim varf accesibil un varf care are numai grad interior sau numai grad exterior (adica nu sunt si muchii care intra si care ies din el).
Pentru un arbore orientat o mutare consta in a alege un varf accesibil si a schimba orientarea tuturor muchiilor ce il contin.
Demonstrati ca printr-un numar finit de mutari se poate ajunge de la orientarea S la orientarea S'.