WikiDer > Кестелік график

Quotient graph

Жылы графтар теориясы, а квоталық график Q график G - бұл шыңдары а блоктары болатын график бөлім шыңдарының G және қай жерде блок B блокпен шектеседі C егер кейбір шыңдар B in шыңына жақын орналасқан C жиегіне қатысты G.[1] Басқаша айтқанда, егер G жиегі бар E және шыңдар жиынтығы V және R болып табылады эквиваленттік қатынас бөлімнен туындаған, содан кейін квоталық графикте шыңдар жиыны бар V/R және жиек жиынтығы {([сен]R, [v]R) | (сен, v) ∈ E(G)}.

Ресми түрде, квота графигі - а объект ішінде санат графиктердің Графиктер категориясы конкретизацияланатын - графикті оның төбелер жиынтығымен салыстыру оны а құрайды бетон категориясы - сондықтан оның объектілері «қосымша құрылымы бар жиынтықтар» ретінде қарастырылуы мүмкін, ал берілген график сәйкес келтірілген графикке сәйкес келеді жиынтық жиынтығы V/R оның шыңының жиынтығы V. Әрі қарай, бар график гомоморфизмі (а квоталық карта) графиктен квота графигіне дейін, әр шыңды немесе шетін өзіне тиесілі эквиваленттік класына жібереді. Интуитивті түрде бұл графтың шыңдары мен шеттеріне «бір-біріне жабыстыруға» (формальды түрде, «анықтау») сәйкес келеді.

Мысалдар

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

Квотенттің арнайы түрлері

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

The конденсация бағытталған граф - бұл квоталық граф, мұндағы қатты байланысты компоненттер бөлімнің блоктарын құрайды. Бұл құрылысты a алу үшін пайдалануға болады бағытталған ациклдік график кез келген бағытталған графиктен.[2]

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

Егер G Бұл жабу графигі басқа графиктің H, содан кейін H болып табылады G. Тиісті бөлімнің блоктары - шыңдарының кері кескіндері H жабу картасының астында. Алайда, карталарды жабудың қосымша талаптары бар, олар квоталарға сәйкес келмейді, бұл карта жергілікті изоморфизм болуы керек.[3]

Есептеудің күрделілігі

Бұл NP аяқталды, берілген n-текс текше график G және параметр к, жоқтығын анықтау үшін G а-ның өлшемі ретінде алуға болады жазықтық график бірге n + к төбелер.[4]

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

  1. ^ Сандерс, Питер; Schulz, Christian (2013), «Жоғары сапалы графикалық бөлу», Графикалық бөлу және графикалық кластерлеу, Contemp. Математика., 588, Amer. Математика. Soc., Providence, RI, 1-17 бет, дои:10.1090 / conm / 588/11700, МЫРЗА 3074893.
  2. ^ Блум, Родерик; Габов, Гарольд Н .; Соменци, Фабио (2006 ж. Қаңтар), «Интенсивті байланысқан компоненттерді талдау алгоритмі n журналn символдық қадамдар », Жүйені жобалаудағы формальды әдістер, 28 (1): 37–56, дои:10.1007 / s10703-006-4341-z.
  3. ^ Гардинер, А. (1974), «Антиподальды жабу графиктері», Комбинаторлық теория журналы, B сериясы, 16: 255–273, дои:10.1016/0095-8956(74)90072-0, МЫРЗА 0340090.
  4. ^ Фариа, Л .; де Фигейредо, C. М. Х .; Mendonça, C. F. X. (2001), «Бөлу саны NP-толық», Дискретті қолданбалы математика, 108 (1–2): 65–83, дои:10.1016 / S0166-218X (00) 00220-1, МЫРЗА 1804713.