Толықтыру және бөлек біріктіру арқылы құрылатын графтар

Кіріспе

Графтар теориясында кограф, немесе комплементке келтірілетін граф, немесе P4-тен бос граф – K1 бір төбелі графынан комплементация және ажыратылған біріктіру арқылы құрастырылатын граф. Яғни, кографтар отбасы – K1 графы кіретін және комплементация мен ажыратылған біріктіру бойынша жабық графтардың ең кіші класы. Кографтар 1970 жылдардан бері бірнеше авторлар тәуелсіз түрде ашқан; алғашқы сілтемелер , , , және олар D* графтары, мұрагерлік Дейси графтары (Джеймс С. Дейсидің ортомодульді торлар туралы жұмысына байланысты) және 2-парлық графтар деп аталды. Оларда ажыратылған біріктіру және комплемент граф операцияларын қамтитын қарапайым құрылымдық жіктелу бар, оны белгіленген ағашпен ықшам түрде бейнелеуге болады, сондай-ақ көптеген мәселелерді, мысалы, ең үлкен кликаны табуды тиімді шешу үшін алгоритмдік түрде қолдануға болады, бұл мәселелер жалпы граф кластарында қиын. Кографтардың ерекше жағдайларына толық графтар, толық екі бөлікті графтар, кластерлік графтар және шекті графтар жатады. Кографтар өз кезегінде қашықтық бойынша мұрагерлік графтар, пермутациялық графтар, салыстыру графтары және толық графтардың ерекше жағдайлары болып табылады.

Басқа сипаттамалар

Кографтардың бірнеше баламалы сипаттамаларын келтіруге болады. Олардың ішінде:

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

Ағаш

Котри – ішкі түйіндері 0 және 1 сандарымен белгіленген ағаш. Кез келген T котриі T-нің жапырақтарын төбелері ретінде қабылдайтын G кографы мен байланысты, және T-нің әрбір түйінінде тамырланған кіші ағаш сол түйінен басталатын жапырақтар жиынымен анықталған G-дегі индукцияланған подграфқа сәйкес келеді: Бір жапырақтан тұратын кіші ағаш бір төбелі индукцияланған подграфқа сәйкес келеді. 0 деп белгіленген түйінге тамырланған кіші ағаш сол түйіннің ұрпақтарымен анықталған подграфтардың бірігіне сәйкес келеді. 1 деп белгіленген түйінге тамырланған кіші ағаш сол түйіннің ұрпақтарымен анықталған подграфтардың қосылысына сәйкес келеді; яғни, біз біріктіруді жасаймыз және әр түрлі кіші ағаштардың жапырақтарына сәйкес келетін әр екі төбе арасына қабырға қосамыз. Сонымен қатар, графтар жиынының қосылысын әрбір графты толықтыру арқылы, толықтырулардың біріктіруін жасау және содан кейін пайда болған біріктіруді толықтыру арқылы құруға болады. Котриден құрылған кографты сипаттаудың тағы бір жолы – егер және тек қана сәйкес жапырақтардың ең төменгі ортақ атасы 1-мен белгіленген болса, екі төбе қабырғамен байланысқан. Керісінше, кез келген кографты осылайша котри арқылы көрсетуге болады. Егер осы ағаштың түбір-жапырақ жолындағы белгілерді 0 мен 1 арасында кезекпен алмастыруды талап етсек, онда бұл бейнелеу бірегей болады.

Есептеу қасиеттері

Кографтарды сызықтық уақытта тануға болады, ал котри ағашын құру үшін модульдік ыдырау, бөлімді жетілдіру, LexBFS немесе бөлінген ыдырау қолданылады. Котри ағашы құрылғаннан кейін, көптеген таныс графиктерге қатысты мәселелерді котри ағаштарындағы қарапайым төменнен жоғарыға қарай есептеулер арқылы шешуге болады. Мысалы, кографтағы ең үлкен кликаны табу үшін, котри ағашының субағашымен көрсетілген әрбір субграфтағы ең үлкен кликаны төменнен жоғарыға қарай есептеңіз. 0 деп белгіленген түйін үшін ең үлкен клика – сол түйіннің ұрпақтары үшін есептелген кликалардың арасындағы ең үлкені. 1 деп белгіленген түйін үшін ең үлкен клика – сол түйіннің ұрпақтары үшін есептелген кликалардың бірігі, ал оның мөлшері ұрпақтардың клика мөлшерлерінің қосындысына тең. Осылайша, котри ағашының әрбір түйінінде сақталған мәндерді кезектесіп максимизациялап және қосып, максималды клика мөлшерін есептеуге болады, ал кезектесіп максимизациялап және біріктірулерді қолдану арқылы максималды кликаны құруға болады. Дәл осындай төменнен жоғарыға қарай ағаш есептеулері ең үлкен тәуелсіз жиынтықты, түк түстеу санын, ең үлкен кликалық жамылғыны және Гамильтондық қасиетті (яғни Гамильтон циклінің болуын) кографтың ағаш бейнелеуінен сызықтық уақытта есептеуге мүмкіндік береді. Кографтардың клика ені шектелгендіктен, Курселл теоремасын графиктердің (MSO1) монодикалық екінші реттік логикасындағы кез келген қасиетті сызықтық уақытта кографтарда тексеру үшін пайдалануға болады. Берілген графиктің k төбесінен және/немесе t қабырғасынан кографқа дейінгі арақашықтығын тексеру мәселесі тұрақты параметрмен шешіледі. Графты k қабырғаны жою арқылы кографқа айналдыру O*(2.415k) уақытында, ал k қабырғаны өңдеу арқылы кографқа айналдыру O*(4.612k) уақытында шешіледі. Егер графиктің ең үлкен индуцирленген кограф субграфы графиктен k төбесін жою арқылы табылса, оны O*(3.30k) уақытында табуға болады. Екі кограф изоморфты болады, егер олардың котри ағаштары (бірдей белгісі бар екі іргелес төбесі жоқ канондық түрінде) изоморфты болса ғана. Осы эквиваленттіліктің арқасында екі кографтың изоморфты екенін олардың котри ағаштарын құрастырып және таңбаланған ағаштар үшін сызықтық уақыт изоморфизмін тексеруді қолдану арқылы сызықтық уақытта анықтауға болады. Егер H – G кографының индуцирленген субграфы болса, онда H өзі кограф болады; H үшін котри ағашын G үшін котри ағашынан кейбір жапырақтарды жойып, содан кейін бір ғана баласы бар түйіндерді басып тастау арқылы құруға болады. Крускалдың ағаш теоремасынан индуцирленген субграф болу қатынасы кографтардағы жақсы квази-реттілік болып табылады. Осылайша, егер кографтардың (мысалы, жазық кографтар) бір суботбасы индуцирленген субграф операциялары бойынша жабық болса, онда оның шекті саны бар. Есептеу тұрғысынан бұл мұндай кіші отбасына мүшелікті тексеруді сызықтық уақытта, берілген графиктің котри ағашында төменнен жоғарыға қарай есептеу арқылы, оның осы тыйым салынған кіші графтардың бірін қамтитынын тексеру арқылы жүзеге асыруға болады. Алайда, екі кографтың мөлшері де өзгермелі болған кезде, олардың біреуінің екіншісінің индуцирленген субграфы екенін тексеру NP-толық мәселе болып табылады. Кографтар бір рет оқылған функцияларды тану алгоритмдерінде маңызды рөл атқарады. Кейбір есептеу мәселелері, егер кіріс кографқа ғана шектелсе, сонымен қатар шешіледі. Мысалы, полиномиалдық уақыт алгоритмдері бар, олар кликалардың санын немесе кографтағы максималды кликалардың санын есептейді.

Cographs may be recognized in linear time, and a cotree representation constructed, using modular decomposition, partition refinement, LexBFS , or split decomposition. Once a cotree representation has been constructed, many familiar graph problems may be solved via simple bottom up calculations on the cotrees. For instance, to find the maximum clique in a cograph, compute in bottom up order the maximum clique in each subgraph represented by a subtree of the cotree. For a node labeled 0, the maximum clique is the maximum among the cliques computed for that node's children. For a node labeled 1, the maximum clique is the union of the cliques computed for that node's children, and has size equal to the sum of the children's clique sizes. Thus, by alternately maximizing and summing values stored at each node of the cotree, we may compute the maximum clique size, and by alternately maximizing and taking unions, we may construct the maximum clique itself. Similar bottom up tree computations allow the maximum independent set, vertex coloring number, maximum clique cover, and Hamiltonicity (that is the existence of a Hamiltonian cycle) to be computed in linear time from a cotree representation of a cograph. Because cographs have bounded clique width, Courcelle's theorem may be used to test any property in the monadic second order logic of graphs (MSO1) on cographs in linear time. The problem of testing whether a given graph is k vertices away and/or t edges away from a cograph is fixed parameter tractable. Deciding if a graph can be k edge deleted to a cograph can be solved in O*(2.415k) time, and k edge edited to a cograph in O*(4.612k). If the largest induced cograph subgraph of a graph can be found by deleting k vertices from the graph, it can be found in O*(3.30k) time. Two cographs are isomorphic if and only if their cotrees (in the canonical form with no two adjacent vertices with the same label) are isomorphic. Because of this equivalence, one can determine in linear time whether two cographs are isomorphic, by constructing their cotrees and applying a linear time isomorphism test for labeled trees. If H is an induced subgraph of a cograph G, then H is itself a cograph; the cotree for H may be formed by removing some of the leaves from the cotree for G and then suppressing nodes that have only one child. It follows from Kruskal's tree theorem that the relation of being an induced subgraph is a well quasi ordering on the cographs. Thus, if a subfamily of the cographs (such as the planar cographs) is closed under induced subgraph operations then it has a finite number of forbidden induced subgraphs. Computationally, this means that testing membership in such a subfamily may be performed in linear time, by using a bottom up computation on the cotree of a given graph to test whether it contains any of these forbidden subgraphs. However, when the sizes of two cographs are both variable, testing whether one of them is an induced subgraph of the other is NP complete. Cographs play a key role in algorithms for recognizing read once functions. Some counting problems also become tractable when the input is restricted to be a cograph. For instance, there are polynomial time algorithms to count the number of cliques or the number of maximum cliques in a cograph.

Санақ

n = 1, 2, 3, ... үшін n төбесі бар байланысты кографтардың саны:
1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ...
n > 1 үшін, әр кографтың өзі немесе оның толықтауыш графының біреуі байланысты болғандықтан, байланыссыз кографтардың саны да осы болады.

Кіші сыныптар

Кез келген толық граф Kn – бір 1 түйіннен және n жапырақтан тұратын котреесі бар кограф болып табылады. Сол сияқты, кез келген толық екібөлікті граф Ka,b – кограф. Оның котреесі 1 түйінге тамырланған, оның екі 0 түйіні бар, біреуі a жапырақ балаларымен, екіншісі b жапырақ балаларымен. Туран графы тең өлшемді тәуелсіз жиынтықтардың біріктірілуі арқылы құрастырылуы мүмкін; осылайша, ол да кограф болып табылады, оның котреесі 1 түйінге тамырланған, және әрбір тәуелсіз жиынтық үшін 0 түйін баласы бар. Кез келген шектік граф – сонымен қатар кограф. Шектік графты қайталап бір төбе қосу арқылы жасауға болады, ол барлық бұрынғы төбелерге қосылуы немесе олардың ешқайсысына да қосылмауы мүмкін; әрбір мұндай операция – котрее құруға мүмкіндік беретін ажыратылған біріктіру немесе біріктіру операцияларының бірі болып табылады.

Жоғары сыныптар

Кографтарды әрбір клика мен максималды тәуелсіз жиынның бос емес қиылысуы бар деген қасиетпен сипаттау, әрбір индукцияланған субграфтың барлық максималды кликаларды қиылыстыратын тәуелсіз жиынды қамтитын күшті кемелді графиктердің анықтамалық қасиетінің күштірек түрі болып табылады. Кографта әрбір максималды тәуелсіз жиын барлық максималды кликаларды қиып өтеді. Осылайша, әрбір кограф күшті кемелді. Кографтардың P4-тен бос екендігі олардың толық реттелгендігін білдіреді. Шындығында, кографтың кез келген төбелік реті – кемелді рет, бұл өз кезегінде максимум кликаны табу және минимум бояуды кез келген ашкөз бояумен және котриялық ыдырату қажеттілігінсіз сызықтық уақытта табуға мүмкіндік береді. Әрбір кограф – арақашықтық мұрагерлік графигі, яғни кографтағы әрбір индукцияланған жол – ең қысқа жол. Кографтарды арақашықтық мұрагерлік графиктер арасында әрбір байланысқан компонентте диаметрі ең көп дегенде екіге тең болатынымен сипаттауға болады. Әрбір кограф сонымен қатар қатарлы-параллель бөлшектік реттің салыстырылатын графигі болып табылады, ол кограф құрылымында қолданылған дизъюнктивті біріктіру және біріктіру операцияларын бөлшектік реттердегі дизъюнктивті біріктіру және ординалдық қосынды операцияларымен алмастыру арқылы алынады. Күшті кемелді графиктер, толық реттелген графиктер, арақашықтық мұрагерлік графиктер және салыстырылатын графиктердің барлығы да кемелді графиктер болғандықтан, кографтар да кемелді болады.