Графтарда жиектерді әдемілеу таңбалау – қарапайым, байланысты графтар үшін маңызды теория. Жиектердің санын, төбелерді ескере отырып, әр төбеге жиектердің сандары қосылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Граф белгілендіруінің түрі
Type of graph labeling
Графтар теориясында, жиектік әдемі белгілендіру – қарапайым, байланысты графтар үшін график белгілендіруінің бір түрі. Онда екі түрлі жиек бірдей екі түрлі төбеге жалғанбайды және ешбір жиек төбені өзіне жалғамайды. Жиектік әдемі белгілендіруді алғаш рет Шэнь Пинг Ло өзінің маңызды еңбегінде енгізген.
In graph theory, an edge graceful labeling is a type of graph labeling for simple, connected graphs in which no two distinct edges connect the same two distinct vertices and no edge connects a vertex to itself. Edge graceful labelings were first introduced by Sheng Ping Lo in his seminal paper.
Анықтама
G графигін қарастыратын болсақ, оның қабырғалары жиынын E(G) деп, ал төбелері жиынын V(G) деп белгілейміз. q – E(G) жиынының, ал p – V(G) жиынының кардиналдығы болсын. Қабырғаларға белгілеу берілгеннен кейін, графтың төбесіне оған жанасқан қабырғалардың белгілерінің қосындысымен, p модулі бойынша белгі беріледі. Яғни, төбеге индукцияланған белгілеу мына формуламен беріледі:
Given a graph G, we denote the set of its edges by E(G) and that of its vertices by V(G). Let q be the cardinality of E(G) and p be that of V(G). Once a labeling of the edges is given, a vertex of the graph is labeled by the sum of the labels of the edges incident to it, modulo p. Or, in symbols, the induced labeling on a vertex is given by
мұнда V(u) – u төбесі үшін алынған мән, ал E(e) – u төбесіне жанасқан e қабырғасының қолданыстағы мәні. Мәселе – 1-ден q-ға дейінгі барлық белгілерді бір рет қолданып, төбелердегі индукцияланған белгілер 0-ден p–1-ге дейін болатын қабырғаларға белгілеуді табу. Басқаша айтқанда, қабырғалар үшін белгілер жиыны {1, 2, ..., q} болуы керек, әр мән бір рет қолданылады, ал төбелер үшін – {0, 1, ..., p–1}. G графигі қабырғалық сүйкімді (edge graceful) деп аталады, егер ол қабырғалық сүйкімді белгілеуге ие болса.
where V(u) is the resulting value for the vertex u and E(e) is the existing value of an edge e incident to u. The problem is to find a labeling for the edges such that all the labels from 1 to q are used once and that the induced labels on the vertices run from 0 to p – 1. In other words, the resulting set of labels for the edges should be {1, 2, , q}, each value being used once, and that for the vertices should be {0, 1, , p – 1}. A graph G is said to be edge graceful if it admits an edge graceful labeling.
Циклдер
Үш төбесі бар циклді қарастырайық. Бұл қарапайым үшбұрыш. Қабырғаларын 1, 2 және 3 деп белгілеп, тікелей тексерсек, төбелерге қойылған белгілермен бірге, бұл қабырғалық әдемі белгілеуді береді. Жолдар сияқты, m тақ болғанда қабырғалық әдемі белгілеу мүмкін, ал m жұп болғанда – мүмкін емес.
Consider the cycle with three vertices, This is simply a triangle. One can label the edges 1, 2, and 3, and check directly that, along with the induced labeling on the vertices, this gives an edge graceful labeling. Similar to paths, is edge graceful when m is odd and not when m is even.
Жолдар
Екі төбесі бар жолды қарастырайық. Мұндағы жалғыз мүмкіндік – графтың жалғыз қабырғасын 1 деп белгілеу. Екі төбедегі индукциялық белгілеу екеуі де 1 болады. Демек, бұл қабырғалық сүйкімді емес. Қабырға мен төбе қосып, үш төбелі жол аламыз. Төбелерді А, В және С деп белгілейік, екі қабырғаны келесідей белгілейміз: АВ қабырғасы 1, ВС қабырғасы 2 деп белгіленеді. Онда А, В және С төбелеріндегі белгілер сәйкесінше 1, 0 және 2 болады. Бұл қабырғалық сүйкімді белгілеу, демек, бұл граф қабырғалық сүйкімді. Сол сияқты, К4 графы қабырғалық сүйкімді емес екенін тексеруге болады. Жалпы, m тақ болса, Pn қабырғалық сүйкімді, ал m жұп болса, қабырғалық сүйкімді емес. Бұл қабырғалық сүйкімділіктің қажетті шартынан туындайды.
Consider a path with two vertices, Here the only possibility is to label the only edge in the graph 1. The induced labeling on the two vertices are both 1. So is not edge graceful. Appending an edge and a vertex to gives , the path with three vertices. Denote the vertices by , , and Label the two edges in the following way: the edge is labeled 1 and labeled 2. The induced labelings on , , and are then 1, 0, and 2 respectively. This is an edge graceful labeling and so is edge graceful. Similarly, one can check that is not edge graceful. In general, is edge graceful when m is odd and not edge graceful when it is even. This follows from a necessary condition for edge gracefulness.
Қажетті шарт
Ло q жиегі және p төбесі бар графтың жиекті әдемі болуы үшін қажетті шартын берді: Бұл төбелердің белгілерінің қосындысы, модуль p бойынша, жиектердің қосындысының екі еселенгеніне теңдігінен туындайды. Бұл графтың жиекті әдемі еместігін көрсету үшін пайдалы. Мысалы, жоғарыда келтірілген жол және цикл мысалдарына осыны тікелей қолдануға болады.
Lo gave a necessary condition for a graph with q edges and p vertices to be edge graceful: This follows from the fact that the sum of the labels of the vertices is twice the sum of the edges, modulo p. This is useful for disproving a graph is edge graceful. For instance, one can apply this directly to the path and cycle examples given above.
Таңдалған қосымша нәтижелер
Питерсен графигі шеттері әдемі емес. Жұлдыз тәрізді граф (орталық түйін және ұзындығы 1-ге тең m қабырғасы) m жұп болғанда шеттері әдемі, ал m тақ болғанда емес. Достық графигі m тақ болғанда шеттері әдемі, ал m жұп болғанда емес. Түздік ағаштар (тереңдігі n, әрбір жапырақ емес түйіні m жаңа төбе шығарады) m кез келген n үшін жұп болғанда шеттері әдемі, ал m тақ болғанда емес. N төбесі бар толық граф, , n жұп сан болмаса ғана шеттері әдемі. Еңкейтілген граф ешқашан шеттері әдемі болмайды.
The Petersen graph is not edge graceful. The star graph (a central node and m legs of length 1) is edge graceful when m is even and not when m is odd. The friendship graph is edge graceful when m is odd and not when it is even. Regular trees, (depth n with each non leaf node emitting m new vertices) are edge graceful when m is even for any value n but not edge graceful whenever m is odd. The complete graph on n vertices, , is edge graceful unless n is singly even, The ladder graph is never edge graceful.