Айналдыру картасы - Rotation map

Жылы математика, а айналу картасы - бұл бағытталмаған жиекті білдіретін функциябелгіленген график, мұнда әр шың өзінің шығатын көршілерін санайды. Айналу карталарын алғаш рет Рейнгольд, Вадхан және Вигдерсон енгізген («Энтропия толқындары, циг-заг графты өнімі және жаңа тұрақты дәрежелі кеңейткіштер», 2002). зиг-заг өнімі және оның қасиеттерін дәлелдеңіз ${ displaystyle v}$ және шеткі затбелгі ${ displaystyle i}$ , айналу картасы ${ displaystyle i}$ көршісі ${ displaystyle v}$ және қайтадан әкелетін шеткі жапсырма ${ displaystyle v}$ .

Анықтама

Үшін Д.- тұрақты график G, айналу картасы ${ displaystyle mathrm {Rot} _ {G}: [N] times [D] rightarrow [N] times [D]}$ келесідей анықталады: ${ displaystyle mathrm {Rot} _ {G} (v, i) = (w, j)}$ егер мен шетінен шығу v әкеледі w, және j шетінен шығу w әкеледіv.

Негізгі қасиеттері

Анықтамадан біз мұны көреміз ${ displaystyle mathrm {Rot} _ {G}}$ бұл ауыстыру, сонымен қатар ${ displaystyle mathrm {Rot} _ {G} circ mathrm {Rot} _ {G}}$ жеке куәлік ( ${ displaystyle mathrm {Rot} _ {G}}$ болып табылады инволюция ).

Ерекше жағдайлар және қасиеттер

Айналдыру картасы әр шыңнан шығатын барлық шеттер әр шыңда кіретін шеттердің белгілері бірдей болатындай етіп таңбаланған жағдайда үнемі белгіленеді. Кез-келген тұрақты графикада кейбір дәйекті белгілер болады.
Айналдыру картасы ${ displaystyle pi}$ - егер сәйкес болса ${ displaystyle forall v mathrm {Rot} _ {G} (v, i) = (v [i], pi (i))}$ . Анықтамадан, а ${ displaystyle pi}$ -айналмалы карта дәйекті түрде белгіленеді.

Сондай-ақ қараңыз

Әдебиеттер тізімі

Рейнгольд, О .; Вадхан, С .; Видгерсон, А. (2000), «Энтропия толқындары, зиг-заг графтық өнімі және жаңа тұрақты дәрежелі кеңейткіштер мен экстракторлар», Информатика негіздеріне арналған 41-ші жыл сайынғы симпозиум: 3–13, arXiv:математика / 0406038, дои:10.1109 / SFCS.2000.892006, ISBN 978-0-7695-0850-4

Reingold, O (2008), «Лог-кеңістіктегі бағытталмаған байланыс», ACM журналы, 55 (4): 1–24, дои:10.1145/1391289.1391291

Рейнгольд, О .; Тревизан, Л .; Вадхан, С. (2006), «жалған кездейсоқ жүрістер тұрақты диграфтарда жүреді және RL мен L проблемасына қарсы», Есептеу теориясы бойынша жыл сайынғы ACM отыз сегізінші симпозиумының материалдары: 457, дои:10.1145/1132516.1132583, ISBN 978-1595931344