| dbo:abstract
|
- A gráfelmélet területén a gráfok kanonikalizációja vagy kanonizációja egy adott G gráf kanonikus alakjának megtalálása. A kanonikus forma egy olyan Canon(G) , ami izomorf G-vel, továbbá minden G-vel izomorf gráfnak is ugyanez a kanonikus alakja. Így tehát a gráfkanonikalizáció problémájának megoldása automatikusan megoldja a gráfizomorfizmus problémáját is: Két gráf, G és H akkor izomorf, ha kanonikus alakjaik, Canon(G) és Canon(H) megegyeznek. A gráfok kanonikus alakja a teljes gráfinvariánsok egyik példája: bármely két izomorf gráf kanonikus alakja megegyezik és bármely két nem izomorf gráf kanonikus alakja különbözik. Megfordítva, bármely teljes gráfinvariáns segítségével megszerkeszthető egy kanonikus alak. Az n csúcsú gráf csúcspontjait megszámozhatjuk 1-től n-ig egész számokkal, így a gráf kanonikus alakja a csúcsainak egy permutációjával is leírható. A gráfok kanonikus formáját kanonikus címkézésnek is nevezik. (hu)
- A gráfelmélet területén a gráfok kanonikalizációja vagy kanonizációja egy adott G gráf kanonikus alakjának megtalálása. A kanonikus forma egy olyan Canon(G) , ami izomorf G-vel, továbbá minden G-vel izomorf gráfnak is ugyanez a kanonikus alakja. Így tehát a gráfkanonikalizáció problémájának megoldása automatikusan megoldja a gráfizomorfizmus problémáját is: Két gráf, G és H akkor izomorf, ha kanonikus alakjaik, Canon(G) és Canon(H) megegyeznek. A gráfok kanonikus alakja a teljes gráfinvariánsok egyik példája: bármely két izomorf gráf kanonikus alakja megegyezik és bármely két nem izomorf gráf kanonikus alakja különbözik. Megfordítva, bármely teljes gráfinvariáns segítségével megszerkeszthető egy kanonikus alak. Az n csúcsú gráf csúcspontjait megszámozhatjuk 1-től n-ig egész számokkal, így a gráf kanonikus alakja a csúcsainak egy permutációjával is leírható. A gráfok kanonikus formáját kanonikus címkézésnek is nevezik. (hu)
|
