Zdravím,
chtěl bych se zeptat jestli nebo spíš jaký použít algoritmus na nutné, ale nepostačující podmínky izomorfimu:
1. |U1| = |U2|: true
2. |H1| = |H2|: false
3. Jsou-li u, v sousední uzly, pak i (u), (v) jsou sousední uzly: true
4. Grafy mají stejnou posloupnost stupňů uzlů: true
5. Pak pro každý uzel v z U platí
– stupeň uzlu v je roven stupni uzlu φ(v): false
– množina stupňů sousedů uzlu v je rovna množině stupňů sousedů
uzlu φ(v): false
6. Pak pro každý sled platí
– obraz sledu je opět sled: false
– obraz tahu je opět tah: true
– obraz cesty je opět cesta: true
– délka sledu zůstává zachována: false
1,2,4 - tyto body jsou mi jasné. Ale dále je to velký otazník. Mám to předělané na objekty i jako matice :) .
U 3 bodu bylo řečeno, že jenom brutal force silou, prohledávání dvojic za použití permutace.
5 a- mi přijde stejná jak 4. 5b mi přijde podobná jako 3.
A u 6 použít matice nebo nějak rekurzivně? :O Děkuji za jakoukoliv radu či nápad.
Offline