Кернеу графигі - Википедия - Voltage graph

Жылы графтар теориясы, а кернеу графигі Бұл бағытталған граф оның жиектері а элементтерімен төңкеріліп таңбаланған топ. Ол формальды түрде a-ға ұқсас күшейту графигі, бірақ ол әдетте қолданылады топологиялық графизм теориясы басқасын көрсетудің ықшам тәсілі ретінде график деп аталады алынған график кернеу графигі.

Кернеу графигі үшін пайдаланылатын топтардың типтік таңдауына екі элементті group тобы жатады2 (анықтау үшін екі жақты қақпақ графиктің), тегін топтар (анықтау үшін әмбебап қақпақ графиктің), г.-өлшемді бүтін торларг. (векторлық қосу кезінде топ ретінде қарастырылады, мерзімді құрылымдарды анықтау үшін г.-өлшемді Евклид кеңістігі ),[1] және ақырлы циклдік топтарn үшін n > 2. Қашан Π циклдік топ болып табылады, кернеу графигін а деп атауға болады циклдық кернеу графигі.

Анықтама

А-ның ресми анықтамасы Π-берілген топ үшін кернеулер графигі Π:

  • А-дан басталады диграф G. (Бағыт тек белгілерде ыңғайлы болу үшін).
  • A Π- доғадағы кернеу G элементтің көмегімен доғаның белгісі х туралы Π. Мысалы, қайда Π = ℤn, затбелгі сан болып табылады мен (модn).
  • A Π-толқынды тағайындау - бұл функция әрбір доғаны белгілейді G Π кернеуімен.
  • A Π- кернеу графигі - бұл жұп осындай G - диграф, ал α - кернеу тағайындау.
  • The кернеу тобы кернеу графигі топ болып табылады Π одан кернеулер тағайындалады.

Кернеу графигінің кернеулері қанағаттандырмайтынын ескеріңіз Кирхгофтың кернеу заңы, тұйықталған жол бойындағы кернеулердің қосындысы 0 (топтың сәйкестендіру элементі), дегенмен, бұл заң төменде сипатталған туынды графиктерге сәйкес келеді. Осылайша, атау біршама жаңылыстыруы мүмкін. Бұл кернеу графиктерінің пайда болуынан қосарланғанға негізделген ағымдағы графиктер туралы топологиялық графизм теориясы.

Алынған график

The алынған график кернеу графигі бұл график оның шың жиыны және оның жиектер жиыны , мұнда жиектің соңғы нүктелері (e, к) солай e құйрығы бар v және бас w болып табылады және .

Диаграммалар үшін кернеу графиктері анықталғанымен, олар кеңейтілуі мүмкін бағытталмаған графиктер әрбір бағытталмаған жиекті қарама-қарсы реттелген жұптармен ауыстыру арқылы және бұл шеттерде топ құрылымында бір-біріне кері белгілердің болуын талап ету арқылы. Бұл жағдайда туынды графиктің қасиеттері болады, оның бағытталған шеттері қарама-қарсы бағытталған шеттерінің жұптарын құрайды, сондықтан алынған графтың өзі бағытталмаған граф ретінде түсіндірілуі мүмкін.

Алынған график - а жабу графигі берілген кернеу графигі. Егер кернеу графигінің шеткі белгісі сәйкестендіру элементі болмаса, онда туынды графиктің шыңдарымен байланысты топ элементтері бояу түстер саны топтық тәртіпке тең болатын алынған графиктің. Маңызды ерекше жағдай екі жақты қақпақ, кернеу графигінің алынған графигі, онда барлық жиектер екі элементті топтың жеке емес элементімен белгіленеді. Топтың реті екі болғандықтан, алынған график бұл жағдайда кепілдендірілген екі жақты.

Көпмүшелік уақыт алгоритмдер а-ның алынған графигінің анықталуымен белгілі - кернеу графигінде кез келген бағытталған циклдар болады.[1]

Мысалдар

Кез келген Кейли графигі топтың Π, берілген жиынтықпен Γ генераторлар, а үшін алынған график ретінде анықталуы мүмкін Π- бір шыңы бар кернеулер графигі және | Γ | әрқайсысы ішіне генераторлардың біреуімен белгіленген өзіндік ілмектер Γ.[2]

The Питерсен графигі a үшін алынған график5- екі шыңы және үш шеті бар гантель түріндегі кернеу графигі: екі шыңды біріктіретін бір шеті, ал әр шыңында бір цикл. Бір циклге 1, екіншісіне 2, ал екі шыңды біріктіретін шеге 0 деп белгіленеді. Жалпы алғанда, бірдей конструкция кез келген жалпыланған Петерсен графигі GP (n,к) 1, 0, және белгілері бар бірдей гантель графигінің алынған графигі ретінде тұрғызу керек к in тобындаn.[3]

Кез келген периодиктің төбелері мен шеттері тесселляция жазықтықтың кернеулері ℤ болатын ақырлы графиктің алынған графигі ретінде құрылуы мүмкін2.

Ескертулер

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

  • Коэн, Эдит; Мегиддо, Нимрод (1989), «Динамикалық графиктердегі циклдарды анықтауға арналған күшті полиномдық уақыт және NC алгоритмдері», Proc. Есептеулер теориясына арналған 21-ші ACM симпозиумы (STOC '89), 523-534 б., дои:10.1145/73007.73057.
  • Гросс, Джонатан Л. (1974), «Кернеу графиктері», Дискретті математика, 9 (3): 239–246, дои:10.1016 / 0012-365X (74) 90006-5.
  • Гросс, Джонатан Л. Такер, Томас В. (1977), «Кернеуді ауыстыру арқылы барлық графикалық жабындарды құру», Дискретті математика, 18 (3): 273–283, дои:10.1016 / 0012-365X (77) 90131-5.
  • Гросс, Джонатан Л. Такер, Томас В. (1987), Топологиялық графика теориясы, Нью-Йорк: Вили.
  • Ивано, К .; Штайглиц, К. (1987), «Периодты құрылымы бар шексіз графиктердегі циклдарды тестілеу», Proc. Есептеулер теориясына арналған ACM 19 жылдық симпозиумы (STOC '87), 46–55 б., дои:10.1145/28395.28401.
  • Косараджу, С.Рао; Салливан, Григорий (1988), «Көпмүшелік уақыттағы динамикалық графиктердегі циклдарды анықтау», Proc. Есептеу теориясы бойынша ACM 20-жылдық симпозиумы (STOC '88), 398–406 б., дои:10.1145/62212.62251.