Графтардың қабырғалық графигі

Кіріспе

Граф, басқа графтың жиектерін бейнелейтін, математикалық ұғым.

Графтар теориясының математикалық саласында, бағытталмаған граф G-нің сызықтық графы L(G) деп басқа графты атайды, ол G жиектері арасындағы байланысты көрсетеді. L(G) келесідей құрылады: G-дегі әрбір жиек үшін L(G)-де төбе жасалады; G-дегі ортақ төбесі бар G-дегі кез келген екі жиек үшін L(G)-де олардың сәйкес төбелері арасында жиек жасалады. "Сызықтық граф" атауы бұл құрылымды қолданған авторлардың еңбектерінен алынған. Сызықтық графты сипаттау үшін басқа терминдер де қолданылады: жабатын граф, туынды, жиектен төбеге дейінгі екіайқас, конъюгат, өкілдік граф және θ-образ, сондай-ақ жиектік граф, алмастыру графигі, қосымша граф және туынды граф. Бір ерекше жағдайды қоспағанда, байланысқан граф G-нің құрылымын оның сызықтық графынан толыққанды қалпына келтіруге болады екені дәлелденді. Осылайша, байланысқан графтың сызықтық графы байланысқан болады. Егер G байланысқан болса, онда оның кез келген екі жиегін жалғайтын жол бар, бұл L(G)-де L(G)-нің кез келген екі төбеін жалғайтын жолға ауысады. Дегенмен, оқшауланған төбелері бар және демек, ажыратылған G графының сызықтық графы байланысқан болуы мүмкін. Сызықтық графта буындық нүкте тек қана егер негізгі графтың бірде-бір шеткі нүктесі бірінші дәрежелі болмаған көпірі болса ғана болады. L(G)-дегі тәуелсіз жиын G-дегі сәйкестікке сәйкес келеді. Атап айтқанда, L(G)-дегі максималды тәуелсіз жиын G-дегі максималды сәйкестікке сәйкес келеді. Максималды сәйкестіктерді көп уақыт ішінде табуға болатындықтан, сызықтық графтардың максималды тәуелсіз жиын проблемасын да шешуге болады, максималды тәуелсіз жиын проблемасының жалпырақталған графтар үшін қиындығына қарамастан. Шеті транзитивті графтың сызықтық графы төбелік транзитивті болады. Бұл қасиетті (мысалы, Петерсен графы сияқты) төбелік транзитивті, бірақ Cayley графтары емес графтар отбасын құру үшін пайдалануға болады: егер G - кемінде бес төбесі бар, екі жақты емес және тақ төбелік дәрежесі бар шеті транзитивті граф болса, онда L(G) төбелік транзитивті емес Cayley граф болады. Егер G графында Эйлер циклі болса, яғни G байланысқан және әр төбесінде жұп саны жиектер болса, онда G-нің сызықтық графы Гамильтондық болады. Дегенмен, сызықтық графтардағы барлық Гамильтондық циклдар Ойлер циклдарынан осылай туындамайды; мысалы, Гамильтондық граф G-нің сызықтық графы өзі Гамильтондық болады, G-нің Ойлерлік болуына қарамастан. Егер екі қарапайым граф изоморфты болса, онда олардың сызықтық графтары да изоморфты болады. Уитни граф изоморфизмі теоремасы барлық байланысқан графтардың бір жұбын қоспағанда, оған кері теореманы ұсынады. Күрделі желілер теориясының контекстінде, кездейсоқ желінің сызықтық графы желінің көптеген қасиеттерін сақтайды, мысалы, кішкентай әлем қасиетін (барлық төбелер жұбы арасында қысқа жолдардың болуын) және оның дәрежелік таралуының пішінін. Күрделі желіде төбелер кластерлерін табудың кез келген әдісін сызықтық графқа қолдануға және оның жиектерін кластерлеуге болатынын атап өтуге болады.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this. Other terms used for the line graph include the covering graph, the derivative, the edge to vertex dual, the conjugate, the representative graph, and the θ obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph. proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph. Thus,
The line graph of a connected graph is connected. If G is connected, it contains a path connecting any two of its edges, which translates into a path in L(G) containing any two of the vertices of L(G). However, a graph G that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph. A line graph has an articulation point if and only if the underlying graph has a bridge for which neither endpoint has degree one. An independent set in L(G) corresponds to a matching in G. In particular, a maximum independent set in L(G) corresponds to maximum matching in G. Since maximum matchings may be found in polynomial time, so may the maximum independent sets of line graphs, despite the hardness of the maximum independent set problem for more general families of graphs. The line graph of an edge transitive graph is vertex transitive. This property can be used to generate families of graphs that (like the Petersen graph) are vertex transitive but are not Cayley graphs: if G is an edge transitive graph that has at least five vertices, is not bipartite, and has odd vertex degrees, then L(G) is a vertex transitive non Cayley graph. If a graph G has an Euler cycle, that is, if G is connected and has an even number of edges at each vertex, then the line graph of G is Hamiltonian. However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way; for instance, the line graph of a Hamiltonian graph G is itself Hamiltonian, regardless of whether G is also Eulerian. If two simple graphs are isomorphic then their line graphs are also isomorphic. The Whitney graph isomorphism theorem provides a converse to this for all but one pair of connected graphs. In the context of complex network theory, the line graph of a random network preserves many of the properties of the network such as the small world property (the existence of short paths between all pairs of vertices) and the shape of its degree distribution. observe that any method for finding vertex clusters in a complex network can be applied to the line graph and used to cluster its edges instead.

Уитнидің изоморфизм теоремасы

Егер екі байланысқан графиктің сызықтық графиктері изоморфты болса, онда негізгі графиктер изоморфты болады, үшбұрыш графигі және тырнақ графигі жағдайында ғана ерекшелік бар, олар изоморфты сызықтық графиктерге ие, бірақ өзіндік изоморфты емес. Үшбұрыш графигі мен тырнақ графигінен басқа, сызықтық графигінің өзінен жоғары симметрия дәрежесіне ие басқа да ерекше кіші графиктер бар. Мысалы, алмаз графигі (екі үшбұрыш бір қабырғаны бөліседі) төрт график автоморфизміне ие, ал оның сызықтық графигі сегіз автоморфизмге ие. Алмаз графигінің суретінде, графикті 90 градусқа бұру графиктің симметриясы емес, бірақ оның сызықтық графигінің симметриясы болып табылады. Дегенмен, мұндай ерекше жағдайлардың барлығында ең көп дегенде төрт төбе бар. Уитни изоморфизмі теоремасының күшейтілген түрінде, төрттен көп төбесі бар байланысқан графиктер үшін, графиктердің изоморфизмі мен олардың сызықтық графиктерінің изоморфизмі арасында біржақты сәйкестік бар екендігі айтылады. Уитни изоморфизмі теоремасының аналогтары көпграфтардың сызықтық графиктері үшін дәлелденген, бірақ бұл жағдайда олар күрделірек. Оларды (қайтадан) ерекше жағдайды (үшбұрыш графигі мен тырнақ графигінен басқа) srg(n(n–1)/2, 2(n–2), n–2, 4) параметрлері бар қатаң тұрақты графиктер ретінде де сипаттауға болады. Үш қатаң тұрақты график, үшбұрыш графигі сияқты бірдей параметрлер мен спектрге ие, оларды график ауыстыру арқылы алуға болады. Екібөлікті графиктің сызықтық графигі кемелді (Кёниг теоремасын қараңыз), бірақ тырнақ графигінің мысалы көрсеткендей, міндетті түрде екібөлікті болуы керек емес. Екібөлікті графиктердің сызықтық графиктері мықты кемелді график теоремасын дәлелдеуде қолданылатын кемелді графиктердің маңызды құрылыс блоктарының бірі болып табылады. Бұл графиктердің ерекше жағдайы – толық екібөлікті графиктердің сызықтық графиктері, мұнаралық графиктер. Толық графиктердің сызықтық графиктері сияқты, оларды бір ерекшелікпен, төбелер саны, қабырғалар саны және жақын және жақын емес төбелер үшін ортақ көршілер саны арқылы сипаттауға болады. Бір ерекше жағдай – үшбұрыш графигі, ол Шриханде графигімен бірдей параметрлерге ие. Егер екібөліктің екі жағында да төбелер саны бірдей болса, онда бұл графиктер қайтадан қатаң тұрақты болады. Жалпы алғанда, егер L(G) кемелді график болса, онда G графигі тура сызықты график деп аталады. Тура сызықты графиктер – үштен үлкен жұп емес ұзындығы бар қарапайым циклды қамтымайтын графиктер. Балама ретінде, граф тура сызықты болып табылады, егер оның әрбір екі байланысты компоненті екібөлікті немесе төртбұрыш (тетраэдр) немесе бір немесе бірнеше үшбұрыштардың кітабы (барлығы ортақ қабырғаны бөліседі) болса ғана. Кез келген тура сызықты график өзі кемелді болады.

If the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph and the claw , which have isomorphic line graphs but are not themselves isomorphic. As well as and , there are some other exceptional small graphs with the property that their line graph has a higher degree of symmetry than the graph itself. For instance, the diamond graph (two triangles sharing an edge) has four graph automorphisms but its line graph has eight. In the illustration of the diamond graph shown, rotating the graph by 90 degrees is not a symmetry of the graph, but is a symmetry of its line graph. However, all such exceptional cases have at most four vertices. A strengthened version of the Whitney isomorphism theorem states that, for connected graphs with more than four vertices, there is a one to one correspondence between isomorphisms of the graphs and isomorphisms of their line graphs. Analogues of the Whitney isomorphism theorem have been proven for the line graphs of multigraphs, but are more complicated in this case. They may also be characterized (again with the exception of ) as the strongly regular graphs with parameters srg(n(n – 1)/2, 2(n – 2), n – 2, 4). The three strongly regular graphs with the same parameters and spectrum as are the Chang graphs, which may be obtained by graph switching from
The line graph of a bipartite graph is perfect (see Kőnig's theorem), but need not be bipartite as the example of the claw graph shows. The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the strong perfect graph theorem. A special case of these graphs are the rook's graphs, line graphs of complete bipartite graphs. Like the line graphs of complete graphs, they can be characterized with one exception by their numbers of vertices, numbers of edges, and number of shared neighbors for adjacent and non adjacent points. The one exceptional case is , which shares its parameters with the Shrikhande graph. When both sides of the bipartition have the same number of vertices, these graphs are again strongly regular. More generally, a graph G is said to be a line perfect graph if L(G) is a perfect graph. The line perfect graphs are exactly the graphs that do not contain a simple cycle of odd length greater than three. Equivalently, a graph is line perfect if and only if each of its biconnected components is either bipartite or of the form (the tetrahedron) or (a book of one or more triangles all sharing a common edge). Every line perfect graph is itself perfect.

Басқа да байланысты графикалық отбасылар

Барлық сызықтық графиктер тырнақсыз графиктер болып табылады, яғни үш жапырақты ағаш түріндегі индукцияланған подграфигі жоқ графиктер. Балама түрінде, бұл G негізгі графигі жұп санды жиектерге ие болса, оның жиектерін екі жиек жолына бөлуге болады дегенді білдіреді. Ағаштардың сызықтық графиктері – нақты тырнақсыз блок графиктер. Бұл графиктер экстремалды график теориясының бір мәселесін шешу үшін қолданылды, яғни берілген жиектер мен төбелер саны бар, ал ең үлкен индукцияланған подграфигі ағаш ретінде мүмкіндігінше кіші болатын график құрастыру үшін. Сызықтық графиктің A жабыстық матрицасының барлық өзіндік мәндері кемінде -2-ге тең. Бұл A-ны , мұндағы J – сызықтық емес графиктің таңбалы инциденттік матрицасы, ал I – бірлік матрица деп жазуға болады. Атап айтқанда, A + 2I – векторлар жүйесінің Грамиан матрицасы: осы қасиетке ие барлық графиктер жалпыланған сызықтық графиктер деп аталады.

Тыйым салынған субграфтар

Сызықтық графиктердің тағы бір сипаттамасы дәлелденді (ал бұрын дәлелсіз хабарланған). Ол сызықтық граф емес, тоғыз минималды граф бар екенін көрсетті, сондықтан сызықтық граф емес кез келген графтың осы тоғыз графтың бірі индукцияланған кіші граф ретінде табылады. Яғни, граф сызықтық граф болып табылады, егер және тек қана оның төбелерінің ешбір жиынтығы осы тоғыз графтың біреуін индукцияламаса. Жоғарыдағы мысалдағы төрт жоғарғы төбе тырнақ (яғни, толық екі бөлікті граф) құрайды, ол тыйым салынған кіші графтардың суретінде жоғарғы сол жақта көрсетілген. Сондықтан, Бейнеке сипаттамасына сәйкес, бұл мысал сызықтық граф бола алмайды. Минималды дәрежесі кемінде 5 болатын графтар үшін, сипаттамада тек суреттегі сол және оң бағандардағы алты кіші граф қана қажет.

Алгоритмдер

және сызықтық графиктерді тану және олардың бастапқы графиктерді қайта құру үшін сызықтық уақыт алгоритмдерін сипаттады. Бұл әдістерді бағытталған графиктерге бейімдеді. Динамикалық графикті сақтау үшін тиімді дерек құрылымын сипаттады, бұл құрылым төбелерді қосу және жою мүмкіндігін қамтамасыз етеді, сонымен қатар кірісті сызықтық график ретінде (бар болған жағдайда) сақтайды, бұл әр қадамда өзгертілген қабырғалар санына пропорционалды уақыт алады. және алгоритмдері сызықтық графиктердің сипаттамаларына негізделген, олар жұп емес үшбұрыштарды қамтиды (сызықтық графиктегі үшбұрыштар, онда үшбұрыш төбелерінің жұп емес санына іргелес тағы бір төбе бар). Дегенмен, алгоритм тек Уитнидің изоморфизм теоремасын пайдаланады. Оның қиындығы қалған график сызықтық график болып қалатын жоюларды анықтау қажеттілігінде, бірақ статикалық тану мәселесіне бейімделгенде тек қосылымдар орындалады және алгоритм келесі қадамдарды атқарады: кіріс графигі L құрастырылады, әр қадамда бұрыннан қосылған кемінде бір төбеге іргелес жаңа төбе таңдалады. L-ге төбелер қосылғанда, 1=L = L(G шартын қанағаттандыратын G графигі сақталады; егер алгоритм сәйкес G графигін таба алмаса, кіріс сызықтық график емес және алгоритм тоқтатылады. G графигінің төбелерінің саны төрт немесе одан аз болғанда, L(G) графигіне v төбесін қосу кезінде сызықтық график бейнесі бірегей болмауы мүмкін. Бірақ мұндай жағдайда кеңейтілген график кішкентай болады, сондықтан оны сызықтық график ретінде тұрақты уақыт ішінде қарапайым іздеу арқылы табуға болады. Басқа G графигінің сызықтық графигіне тең үлкен L графигіне v төбесін қосатын болсақ, S, L-дегі v төбесінің көршілеріне сәйкес G графигінің ішкі графигі болады. S графигінде бір төбеден немесе бір-біріне іргелес емес екі төбеден тұратын төбелік жабын бар екенін тексеріңіз. Егер жабында екі төбе болса, G графигіне осы екі төбені жалғайтын (v төбесіне сәйкес) қабырға қосылып, кеңейтіледі. Егер жабында тек бір төбе болса, онда осы төбеге іргелес жаңа төбе G графигіне қосылады. Әр қадам тұрақты уақыт алады немесе v төбесінің көршілерінің санына пропорционалды өлшемдегі S графигінде төбелік жабынды табуды қамтиды. Осылайша, алгоритмнің жалпы уақыты барлық төбелердің көршілерінің санының қосындысына пропорционалды, ал бұл (қол алысу леммасы бойынша) кіріс қабырғаларының санына пропорционалды.

and described linear time algorithms for recognizing line graphs and reconstructing their original graphs. generalized these methods to directed graphs. described an efficient data structure for maintaining a dynamic graph, subject to vertex insertions and deletions, and maintaining a representation of the input as a line graph (when it exists) in time proportional to the number of changed edges at each step. The algorithms of and are based on characterizations of line graphs involving odd triangles (triangles in the line graph with the property that there exists another vertex adjacent to an odd number of triangle vertices). However, the algorithm of uses only Whitney's isomorphism theorem. It is complicated by the need to recognize deletions that cause the remaining graph to become a line graph, but when specialized to the static recognition problem only insertions need to be performed, and the algorithm performs the following steps:
Construct the input graph L by adding vertices one at a time, at each step choosing a vertex to add that is adjacent to at least one previously added vertex. While adding vertices to L, maintain a graph G for which 1=L = L(G); if the algorithm ever fails to find an appropriate graph G, then the input is not a line graph and the algorithm terminates. When adding a vertex v to a graph L(G) for which G has four or fewer vertices, it might be the case that the line graph representation is not unique. But in this case, the augmented graph is small enough that a representation of it as a line graph can be found by a brute force search in constant time. When adding a vertex v to a larger graph L that equals the line graph of another graph G, let S be the subgraph of G formed by the edges that correspond to the neighbors of v in L. Check that S has a vertex cover consisting of one vertex or two non adjacent vertices. If there are two vertices in the cover, augment G by adding an edge (corresponding to v) that connects these two vertices. If there is only one vertex in the cover, then add a new vertex to G, adjacent to this vertex. Each step either takes constant time, or involves finding a vertex cover of constant size within a graph S whose size is proportional to the number of neighbors of v. Thus, the total time for the whole algorithm is proportional to the sum of the numbers of neighbors of all vertices, which (by the handshaking lemma) is proportional to the number of input edges.

Медиалдық графиктер мен құйқалас көпбұрыштар

Егер жазықтық граф G-нің ең жоғары төбелік дәрежесі үш болса, оның сызықтық графигі жазықтық болады, және G-нің кез келген жазықтық енгізілуі L(G) енгізіліміне дейін кеңейтілуі мүмкін. Дегенмен, жоғары дәрежелі жазықтық графтар бар, олардың сызықтық графиктері жазықтық емес. Мұндай графтарға, мысалы, 5 жұлдызы, тұрақты бесбұрыш ішінде қиылыспайтын екі диагональ қосу арқылы құрылған «асыл тас» графигі, және төрт немесе одан да көп дәрежелі төбелері бар барлық дөңгелек көпжақтар жатады. Басқаша құрылым – медиалдық граф, ең жоғары үш дәрежелі жазықтық графтар үшін сызықтық графпен сәйкес келеді, бірақ әрқашан жазықтық болып табылады. Оның төбелері сызықтық графтың төбелерімен бірдей, бірақ қабырғалары азырақ болуы мүмкін: медиалдық графтың екі төбесі тек қана сәйкес келетін екі қабырға жазық енгізілімнің бір бетінде тікелей жалғасқан жағдайда ғана көршілес болады. Жазық графтың дуалды графигінің медиалдық графигі бастапқы жазық графтың медиалдық графигімен бірдей. Түрақты немесе қарапайым көпжақтар үшін медиалдық граф операциясын геометриялық түрде көпжақтың әрбір төбесін оған жанасқан барлық қабырғаларының орта нүктелері арқылы өтетін жазықтықпен кесу арқылы көрсетуге болады. Бұл операция екінші қиыңдау, дегенеративті қиыңдау немесе түзету деп аталады.

Жалпы графиктер

Граф G-нің толық графигі T(G), граф G-нің элементтерін (төбелерін немесе қабырғаларын) өзінің төбелері ретінде қабылдайды, және егер олар ортақ төбесіне тиісті немесе жапсарлас болса, онда екі элемент арасында қабырға болады. Толық графты граф G-нің әр қабырғасын бөліп, содан кейін бөлінген графтың квадратын есептеу арқылы да алуға болады.

Мультиграфтар

G-дің сызықтық графының түсінігі G мультиграф болған жағдайда да кеңейтілуі мүмкін. Мұндай жағдайда, осы графтардың сипаттамалары оңайлатылады: кликалық бөліктер арқылы сипаттамада енді екі төбе бірдей кликаға тиесілі болуына қатысты шектеулер болмайды, ал тыйым салынған графтар арқылы сипаттамада тоғыз емес, жеті тыйым салынған граф болады. Дегенмен, мультиграфтар үшін бірдей сызықтық графқа ие, бірақ изоморфты емес графтардың саны көбірек. Мысалы, толық екі бөлікті графтың сызықтық графы дипольдық граф пен Шеннон мультиграфының сызықтық графымен бірдей болады, егер олардың жиектерінің саны бірдей болса. Бірақ, осы жағдайда да Уитнидің изоморфизм теоремасына ұқсас теоремалар шығаруға болады.

Сызық диграфтары

Сонымен қатар, сызықтық графиктерді бағытталған графиктерге жалпылауға болады. Егер G бағытталған график болса, оның бағытталған сызық графигі немесе сызық диграфы G-дің әр қабырғасы үшін бір төбеден тұрады. G-дегі u-ден v-ге және w-ден x-ке бағытталған қабырғаларды көрсететін екі төбе, егер v = w болса, сызық диграфында uv-ден wx-ке қабырғамен байланысады. Яғни, G-дің сызық диграфындағы әрбір қабырға G-дегі екі қабырғалы бағытталған жолды көрсетеді. Де Брюйн графиктері толық бағытталған графиктен бастап, бағытталған сызық графиктерін құрастыру процесін қайталау арқылы құрастырылуы мүмкін.

Салмақты сызықтық графиктер

L(G) сызықтық графигінде бастапқы G графигіндегі k дәрежесіндегі әр түйін сызықтық графикте k(k − 1)/2 жиекті жасайды. Көптеген талдау түрлері үшін бұл G-дегі жоғары дәрежелі түйіндер L(G) сызықтық графигінде артық көрсетілетінін білдіреді. Мысалы, бастапқы G графигінің түйіндері бойынша кездейсоқ жүріп өтуді қарастырайық. Бұл кейбір жиілік f бар e жиегімен өтеді. Екінші жағынан, бұл e жиегі L(G) сызықтық графигінде бірегей түйінге, мысалы v-ге бейнеленеді. Егер біз енді сызықтық графиктің түйіндері бойынша осы типтегі кездейсоқ жүрісті орындасақ, v түйінінің жиілігі f-тен мүлдем өзгеше болуы мүмкін. Егер G-дегі e жиегіміз O(k) дәрежелі түйіндерге қосылса, ол сызықтық графикте L(G) жиірек кезігеді. Басқаша айтқанда, Уитни графтарының изоморфизм теоремасы сызықтық графтың бастапқы G графигінің топологиясын әрқашан сенімді түрде кодтайтынын кепілдейді, бірақ бұл екі графтың динамикасының қарапайым қатынасқа ие екеніне кепілдік бермейді. Бір шешім – салмақты сызықтық графикті, яғни салмақты жиектері бар сызықтық графикті құру. Мұны жасауға бірнеше табиғи жолдар бар. Мысалы, егер G графигіндегі d және e жиектері v түйінінде k дәрежесімен жанасса, онда L(G) сызықтық графигінде d және e түйіндерін жалғастыратын жиекке салмақ 1/(k − 1) беруге болады. Осылайша G-дегі әрбір жиектің (егер бір шетінің де 1-дәрежелі түйінмен байланысы болмаса) L(G) сызықтық графигінде 2 күші болады, бұл жиектің G-дегі екі шетіне сәйкес келеді. Бұл салмақты сызықтық графиктің анықтамасын бастапқы G графигі бағытталған немесе тіпті салмақталған жағдайларға дейін кеңейту оңай. Барлық жағдайларда L(G) сызықтық графигі бастапқы G графигінің динамикасын да, топологиясын да көрсететінін қамтамасыз ету қажет.

Гиперграфтардың сызықтық графиктері

Гиперграфтың қабырғалары кез келген жиындар жиынтығын құрауы мүмкін, сондықтан гиперграфтың сызықтық графигі осы жиынтықтардың қиылысу графигімен сәйкес келеді.

Бірлеспе графигі

G-дің ажыратылған графигі, D(G) деп белгіленеді, мынадай тәсілмен құрылады: G-дегі әрбір қабырға үшін D(G)-де төбе жасаңыз; G-дегі ортақ төбесі жоқ әрбір екі қабырға үшін D(G)-де олардың сәйкес төбелері арасында қабырға жасаңыз. Басқаша айтқанда, D(G) – L(G) графигінің толықтыру графигі. D(G)-дегі клика L(G)-дегі тәуелсіз жиынға сәйкес келеді, және керісінше.