Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Шеңберлік диаграмманың қиылысу графигі
диаграмма
басқа диаграммалар
Intersection graph of a chord diagram
the chart
other diagrams
Графтар теориясында шеңберлік граф – бұл шеңберлік диаграмманың қиылысу графигі. Яғни, бұл бағытталмаған граф, оның төбелері шеңбердің шекті хордалар жиымымен байланыстырылуы мүмкін, егер және тек қана сәйкес хордалар бір-бірін кесіп өткенде екі төбе іргелес болады.
In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.
Хроматикалық саны
Дөңгелек графиктің хроматикалық саны – екі қиылысқан хорданың түсі бірдей болмауы үшін оның хордаларын бояуға қолданылатын ең аз түстер саны. Дөңгелек графиктің кез келген үлкен саны хордалары бір-бірін қиып өтетіндей етіп құруға болатындықтан, дөңгелек графиктің хроматикалық саны кез келгендей үлкен болуы мүмкін, ал дөңгелек графиктің хроматикалық санын анықтау NP-толық мәселе. Дөңгелек графикті төрт түспен бояуға болатынын тексеру де NP-толық болып табылады. Бір автор үш түспен бояуды көп уақытта табуға болатынын айтқан, бірақ оның нәтижесін сипаттаған жазуында көптеген егжей-тегжейлдер қалдырылған. Бірнеше авторлар шеңберлік графиктің шектеулі подкластарын азырақ түстермен бояу мәселелерін зерттеді. Атап айтқанда, k немесе одан да көп хордалардың жиынтығы бір-бірін қиып өспейтін дөңгелек графиктің графигін азырақ түстермен бояуға болады. Мұны былай айтуға болады: дөңгелек графиктің шектеулілігі бар. K = 3 болған жағдайда (яғни үшбұрышсыз дөңгелек графиктің жағдайында) хроматикалық сан ең көп дегенде бес болады, және бұл нақты: барлық үшбұрышсыз дөңгелек графикті бес түспен бояуға болады, сонымен қатар бес түс қажет болатын үшбұрышсыз дөңгелек графиктің мысалдары бар. Егер дөңгелек графиктің кемінде бес циклдық ұзындығы болса (яғни үшбұрышсыз және төрт төбелі циклдары жоқ болса), оны ең көп дегенде үш түспен бояуға болады. Үшбұрышсыз квадрат графикті бояу мәселесі, ағаштардың декарт көбейтілімдерінің изометриялық подграфтары ретінде квадрат графикті бейнелеу мәселесімен эквивалентті; осы сәйкестікте, бояудағы түстер саны көбейтілімнің бейнеленгеніндегі ағаштар санына сәйкес келеді.
The chromatic number of a circle graph is the minimum number of colors that can be used to color its chords so that no two crossing chords have the same color. Since it is possible to form circle graphs in which arbitrarily large sets of chords all cross each other, the chromatic number of a circle graph may be arbitrarily large, and determining the chromatic number of a circle graph is NP complete. It remains NP complete to test whether a circle graph can be colored by four colors. claimed that finding a coloring with three colors may be done in polynomial time but his writeup of this result omits many details. Several authors have investigated problems of coloring restricted subclasses of circle graphs with few colors. In particular, for circle graphs in which no sets of k or more chords all cross each other, it is possible to color the graph with as few as colors. One way of stating this is that the circle graphs are bounded. In the particular case when k = 3 (that is, for triangle free circle graphs) the chromatic number is at most five, and this is tight: all triangle free circle graphs may be colored with five colors, and there exist triangle free circle graphs that require five colors. If a circle graph has girth at least five (that is, it is triangle free and has no four vertex cycles) it can be colored with at most three colors. The problem of coloring triangle free squaregraphs is equivalent to the problem of representing squaregraphs as isometric subgraphs of Cartesian products of trees; in this correspondence, the number of colors in the coloring corresponds to the number of trees in the product representation.
Қолданбалар
Дөңгелек графиктер VLSI физикалық дизайнында "екі терминалдық қорапша маршрутизациясы" деп аталатын сымдарды маршрутизациялаудың ерекше жағдайының абстрактілі бейнесі ретінде туындайды. Бұл жағдайда маршрутталмайтын аймақ тіктөртбұрыш болады, барлық желілер екі терминалды, ал терминалдар тіктөртбұрыштың периметріне орналастырылады. Осы желілердің қиылысу графигі дөңгелек график екендігі анық көрінеді. Сымдарды маршрутизациялау кезеңінің мақсаттарының бірі – әртүрлі желілердің электрлік тұрғыдан оқшауланғанын қамтамасыз ету және олардың қиылысу мүмкіндігі бар бөліктері әртүрлі өткізгіш қабаттарда орналастырылуы керек. Сондықтан дөңгелек графиктер осы маршрутизация мәселесінің әртүрлі аспектілерін қамтиды. Дөңгелек графиктерді түстеуді кез келген графиктердің кітапқа ендіруін табу үшін де пайдалануға болады: егер берілген G графигінің төбелері шеңберде орналасса, ал G қабырғалары шеңбердің хордаларын құраса, онда осы хордалардың қиылысу графигі дөңгелек график болады және осы дөңгелек графикті түстеу берілген шеңберлік орналасуды сақтайтын кітапқа ендіруге тең. Бұл эквиваленттілікте түстеудегі түстер саны кітаптағы беттер санына сәйкес келеді.
Circle graphs arise in VLSI physical design as an abstract representation for a special case for wire routing, known as "two terminal switchbox routing". In this case the routing area is a rectangle, all nets are two terminal, and the terminals are placed on the perimeter of the rectangle. It is easily seen that the intersection graph of these nets is a circle graph. Among the goals of wire routing step is to ensure that different nets stay electrically disconnected, and their potential intersecting parts must be laid out in different conducting layers. Therefore circle graphs capture various aspects of this routing problem. Colorings of circle graphs may also be used to find book embeddings of arbitrary graphs: if the vertices of a given graph G are arranged on a circle, with the edges of G forming chords of the circle, then the intersection graph of these chords is a circle graph and colorings of this circle graph are equivalent to book embeddings that respect the given circular layout. In this equivalence, the number of colors in the coloring corresponds to the number of pages in the book embedding.
Байланысты графикалық кластар
График шеңберлік граф болып табылады, егер және тек егер ол тура сызықтағы интервалдар жиынтығының қабаттасу графигі болса. Бұл – төбелері интервалдарға сәйкес келетін график, егер екі интервал бір-бірін жапса, бірақ ешқайсысы екіншісін қамтып алмайтын болса, онда екі төбе жиекпен қосылады. Тұра сызықтағы интервалдар жиынтығының қиылысу графигі интервалдық граф деп аталады. Жазықтықтағы қисықтардың қиылысу графиктері болып табылатын жол графиктері шеңберлік графтарды ерекше жағдай ретінде қамтиды. Кез келген қашықтық мұрагерлік графигі – шеңберлік граф, сондай-ақ кез келген алмастыру графигі және кез келген бейтараптық графигі де шеңберлік граф болып табылады. Кез келген сыртқы жазықтық графигі де шеңберлік граф болып табылады. Шеңберлік графтар көпбұрышты шеңберлік графтармен, бір шеңберге ішкі жазылған көпбұрыштардың қиылысу графиктерімен жалпыланады.
A graph is a circle graph if and only if it is the overlap graph of a set of intervals on a line. This is a graph in which the vertices correspond to the intervals, and two vertices are connected by an edge if the two intervals overlap, with neither containing the other. The intersection graph of a set of intervals on a line is called the interval graph. String graphs, the intersection graphs of curves in the plane, include circle graphs as a special case. Every distance hereditary graph is a circle graph, as is every permutation graph and every indifference graph. Every outerplanar graph is also a circle graph. The circle graphs are generalized by the polygon circle graphs, intersection graphs of polygons all inscribed in the same circle.