Доғалық диаграмма - Arc diagram - Wikipedia

Доғасының диаграммасы Голднер - Харари графигі. Қызыл сызық сызығы бұл графикті Гамильтонианға айналдыру үшін қай жерге бөлінгенін көрсетеді.

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

Суреттердің осы түріне арналған «доға диаграммасы» сөз тіркесін пайдалану осыған ұқсас диаграмма түрін қолдану арқылы жүреді Ваттенберг (2002) жіптердегі қайталану заңдылықтарын көзге елестету, доғаның көмегімен тең қосалқы жолдардың жұптарын қосу. Алайда графикалық сурет салудың бұл стилі өз атына қарағанда әлдеқайда көне, жұмысынан басталады Саати (1964) және Николсон (1968), зерттеу үшін доғалық диаграммаларды қолданған графиктердің сандарын айқастыру. Доғалық диаграммалар үшін ескі, бірақ аз қолданылатын атау сызықтық ендірулер.[1]

Heer, Bostock & Ogievetsky (2010) доға диаграммалары «графиктің жалпы құрылымын екі өлшемді макет сияқты тиімді жеткізбеуі мүмкін» деп жазыңыз, бірақ олардың орналасуы графиктің төбелерімен байланысты көп айнымалы деректерді бейнелеуге мүмкіндік береді.

Пландық графиктер

Қалай Николсон (1968) бақылауларына сәйкес, графиктің жазықтыққа әрбір енуі қиылысу санын өзгертпестен доға диаграммасына айналуы мүмкін. Атап айтқанда, әрқайсысы жазықтық график жазық доғаның диаграммасы бар. Алайда, бұл ендіру үшін оның кейбір шеттері үшін бірнеше шеңберді қолдану қажет болуы мүмкін.

Егер график қиылыстарсыз сызылса, онда әр шеті жеке жарты шеңбер болатын доға диаграммасы қолданылады, онда сызба екі беттен тұрады кітап енгізу, тек үшін мүмкін нәрсе субхамильтон графиктері, жоспарлы графиктердің ішкі жиыны.[2] Мысалы, а максималды жоспарлы график егер онда а бар болса, осындай ендірмесі бар Гамильтон циклі. Демек, сияқты Гамильтон емес максималды жазықтық график Голднер - Харари графигі бір шетіне бір жарты шеңберден тұратын жазық ендірме болуы мүмкін емес. Берілген графиктің осы типтегі доға сызбасының бар-жоғын тексеру (немесе эквивалентті, егер ол екі сандық болса да) NP аяқталды.[3]

Алайда, әрбір жазықтық графиктің доға диаграммасы бар, онда әр шеті а түрінде салынады биарк ең көп дегенде екі жарты шеңбер. Бәрінен де күшті ст-жоспарлы бағытталған график (жазықтық бағытталған ациклдік график бір көзі және бір раковинасы бар, екеуі де сыртқы жағында) доғаның диаграммасы бар, онда әр шеті монотонды қисықты құрайды, бұл қисықтар шыңның бір шетінен екінші шетіне қарай бағытталған.[4] Бағытталмаған жазықтық графиктер үшін доға диаграммасын құрудың бір тәсілі - бір сызықта екі жарты шеңбер болып, графикке бөлу және алынған графикте болатындай етіп қосымша шеттер қосу керек. Гамильтон циклі (және әр жиек ең көп дегенде бір-бірінен бөлінетін етіп) және Гамильтон циклындағы төбелердің орналасуын сызық бойымен ретке келтіру ретінде қолдану керек.[5]

Өткелдерді азайту

Берілген графиктің доға диаграммасының бір жиегінде бір жартылай шеңбері бар және қиылыстары жоқтығын тексеру NP аяқталғандықтан, ол NP-hard өтпелер санын азайтуға мүмкіндік беретін осы типтегі доға диаграммасын табу. Бұл қиылысуды минимизациялау проблемасы, егер сызық бойындағы шыңдардың реті бекітілген болса да, жазық емес графиктер үшін NP-қиын болып қалады.[1] Алайда, тіркелген тапсырыс жағдайында, қиылысусыз ендіру (егер ол бар болса) мәселені полиномдық уақытқа аудару арқылы табылуы мүмкін 2-қанағаттанушылық проблема, онда айнымалылар әр доғаның орналасуын білдіреді және шектеулер қиылысқан доғаларды шыңның бір жағына орналастыруға жол бермейді.[6] Сонымен қатар, бекітілген тапсырыс жағдайында қиылысуды азайту ендіру болуы мүмкін жуықталған шешу арқылы максималды кесу жартылай шеңберлерді және олардың ықтимал қиылыстарын бейнелейтін көмекші графиктегі мәселе (немесе эквивалентті, MAX2SAT 2-қанағаттылық данасының нұсқасын жақындату арқылы).[7]

Чимиковски және шоп (1996), Чимиковский (2002), және Ол, Sykora & Vrt'o (2005) аз қиылысқан доға диаграммаларын табуға арналған эвристиканы талқылау.

Сағат тілімен бағытталу

Суреттері үшін бағытталған графиктер, жалпы шарт - әр доғаны сағат тілінің бағытымен салу, осылайша тізбектегі ертеректен кейінгі шыңға бағытталған доғалар шың сызығының үстінде, ал кейіннен ертерек шыңға бағытталған доғалар төменде сызылады. сызық. Бұл сағат тіліне бағытталған бағдарлау сызбасы басқа графикалық сурет салу стилінің бөлігі ретінде жасалған Фекете және басқалар. (2003) және доға диаграммаларына қолданылады Pretorius & van Wijk (2007).

Басқа мақсаттар

Доғалық диаграммалар пайдаланылды Брендтер (1999) көзге елестету күй диаграммасы а ауысым регистрі, және Джиджев және Вртьо (2002) екенін көрсету үшін қиылысу нөмірі әрбір графиктің кем дегенде квадраты болады ені.

Ескертулер

  1. ^ а б Масуда және т.б. (1990).
  2. ^ Жартылай шеңберлерді кітап ендірулерінде шеткі орналасуға қолданған Бернхарт және Кайнен (1979), бірақ доғалық диаграммалардың екі парақты кітап ендірулерімен нақты байланысы байланысты сияқты Масуда және т.б. (1990).
  3. ^ Чунг, Лейтон және Розенберг (1987).
  4. ^ Джордано және т.б. (2007).
  5. ^ Бекос және т.б. (2013).
  6. ^ Эфрат, Ертен және Кобуров (2007).
  7. ^ Чимиковски және Муми (2007).

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