Монохроматикалық үшбұрыш - Monochromatic triangle

Шеттерінің бөлімі толық граф Қ5 үшбұрышсыз екі ішкі жиынға

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

Проблеманы шешу

Монохроматтық үшбұрыш мәселесі V түйіні бар жиек жиегі және шегі жиегі бар n түйіні бар G (V, E) графигін енгізу ретінде қабылдайды. Шығарылым логикалық мән болып табылады, егер G жиектерінің жиектерін екі бөлінбеген жиынға бөлуге болатын болса E1 және E2, сондықтан G1 (V, E1) және G2 (V, E2) екі подграфтардың екеуі де үшбұрышсыз графиктер, ал басқаша жалған. Бұл шешім мәселесі болып табылады NP аяқталды.[1]

Бірнеше түстерге жалпылау

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

Рэмси теоремасымен байланыс

Авторы Рэмси теоремасы, кез келген ақырлы сан үшін к түстер болса, онда сан бар n толық графиктері n немесе одан да көп шыңдарда үшбұрышсыз жиек бояғыштары жоқ к түстер. Үшін к = 2, сәйкес мән n болып табылады 6. Яғни, толық графиктегі монохроматикалық үшбұрыштың есебіне жауап Қ6 жоқ.

Параметрленген күрделілік

Монохроматикалық үшбұрыштың есебін монадалық екінші ретті графиктердің логикасы (MSO2) логикалық формула бойынша, жиектерінің барлығы бірдей бөлімге жататын үш өзара іргелес шыңдар болмайтындай етіп, екі ішкі жиынға шеттердің бөлінуінің болуын растайды. Бұдан шығады Курсель теоремасы монохроматикалық үшбұрыштың есебі қозғалмайтын параметр шектелген графиктер бойынша кеңдік. Дәлірек айтсақ, есепті шешудің алгоритмі бар, оның жұмыс уақыты кіру графигінің төбелерінің саны жылдамдықтың тез өсетін, бірақ есептелетін функциясына көбейтіледі.[2]

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

  1. ^ Гари, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютерлер және қиындықтар: NP-толықтығы теориясының нұсқаулығы, В.Х. Фриман, ISBN  978-0-7167-1045-5. A1.1: GT6, 191-бет.
  2. ^ Арнборг, Стефан; Лагергрен, Дженс; Seese, Detlef (1988), «Ағаштармен ыдырайтын графиктер үшін қиындықтар (кеңейтілген реферат)», Автоматтар, тілдер және бағдарламалау (Тампере, 1988), Информатикадағы дәрістер, 317, Берлин: Шпрингер, 38-51 б., дои:10.1007/3-540-19488-6_105, МЫРЗА  1023625.