Естествено стреми да предостави на структурата в процес на разглеждане на графиката с помощта на графика на по-малък размер и по-опростена структура. Полезно е да се ориентирате бързо да графиките, които често се намират. Ние вече са въведени, за да се обозначи пълните графика Kr и Cr допълнения ", прост цикъл КН и Pn проста схема, както и пълното двустранно графично Km, п.
Този раздел графики G1 и G2 са несвързани набори от върховете V1 и V2 и несвързани комплекти X1 и X2 ръбове.
съюз G1ÈG2 е графика на импулси множество от върха, който е V = V1ÈV2. и множество ребра има X = X1ÈX2
Съединение брои въведени Zykov - предназначена G1 + G2, G 1 се състои отÈG2 и всички ръбове свързващи V1 и V2. По-специално, К m, п = Km + Kn- Тези операции са показани на фигурата. където G1 = К2 = Р2 и G2 = K1,2 = P3
Ако G - свързан графика, след определен НГ графика с п компоненти, всеки от които е изоморфни до G. Всяка графика могат да бъдат написани като UniGi, където Gi е различен от GJ, защото! = J. Например, изключен графика е показано на фигурата може да се запише като 4K1 È ZK2 È 2K3 È K1,2
Има няколко операции на графики G1 и G2, които образуват графика G с множеството от върховете равни на декартовата продукт Вл X V2. Сред тях, на продукта (или декартови продукт), съставът (или лексикографска продукт).
За да се определи продукт G1xG2 разглежда всички два върха ф = (U1, U2) и V = (v1, v2) от V = V1 X V2. Върхове U и V са съседни в G1XG2 ако и само ако [u1 = v1 и U2 прил v2] или [u2 = v2 и u1 прил u1]. Произведението графики G1 = Р2 и G2 = P3 показани
Състав G = G1 [G2] има V = Vi х V2 като множество върхове и връх ф = (U1, U2) е в непосредствена близост до V = (v1, v2), ако и само ако [u1 asj v1] или [u1 = v1 и U2 прил v2]. За графики G1 и G2, показано на фигурата, две състави G1 [G2] и G2 [G1], който очевидно не са изоморфни, показан на фигура
Ако G1 и G2 - е (p1, q1) - и (Р2, q2) -graphs съответно, е възможно да се намери броя на върховете и броя на ръбовете в получената графика (виж таблица 2.2). За всяка от посочените по-горе операции.
брой върхове брой ръбове
Свързани статии