Кіріспе
Граф элементтеріне белгілер тағайындау
Граф теориясының математикалық саласында графты белгілеу – дәстүрлі түрде бүтін сандармен көрсетілген белгілерді графтың қабырғалары мен/немесе төбелеріне тағайындау. Формальды түрде, 1=G = (V, E) графигі берілгенде, төбелік белгілеу – V төбелерінен белгілер жиынына функция болып табылады; мұндай функциясы анықталған граф төбелік белгіленген граф деп аталады. Сол сияқты, қабырғалық белгілеу – бұл қабырғалар жиынынан белгілер жиынына функция. Бұл жағдайда граф қабырғалық белгіленген граф деп аталады. Егер қабырғалық белгілер реттелген жиынның мүшелері болса (мысалы, нақты сандар), онда ол салмақты граф деп аталуы мүмкін. Ерекше нақтыланбаған жағдайда, белгіленген граф термині әдетте барлық белгілері әртүрлі болатын төбелік белгіленген графты білдіреді. Мұндай графты тізбекті бүтін сандармен белгілеуге болады, мұнда – графтың төбелерінің саны. Жоғарыдағы анықтамада граф – шекті бағытталмаған қарапайым граф ретінде түсініледі. Дегенмен, белгілеу ұғымын графтардың барлық кеңейтулері мен жалпыламаларына қолдануға болады. Мысалы, автоматтар теориясы мен формальды тілдер теориясында белгіленген көпграфтарды қарастыру ыңғайлы, яғни, төбелер жұбы бірнеше белгіленген қабырғалармен байланыстырылуы мүмкін.
Тарих
Көптеген график таңбалаулардың бастауы Александр Розаның 1967 жылғы мақаласында ұсынылған таңбалауларға саяды. Роза үш түрлі таңбалауды анықтады, оларды ол α, β және ρ таңбалаулары деп атады. β таңбалаулары кейіннен Соломон Голомб тарапынан "әдемі" деп қайта аталды, және осы атау содан бері кеңінен танымал болды.
Жақсы таңбалау
Граф сәнді деп аталады, егер оның төбелері 0-ден бастап, графтың өлшеміне дейін нөмірленген болса, және егер бұл төбелерді нөмірлеу 1-ден бастап графтың қабырғаларын нөмірлеуге әкелсе. Кез келген қабырға e үшін, e қабырғасының нөмірi e-ге жақын жатқан екі төбелердің нөмірлерінің арасындағы оң айырмашылық болып табылады. Яғни, егер e қабырғасы i және j нөмірленген төбелерге жақын болса, онда e нөмірі |i - j| болады. Осылайша, G = (V, E) графигі сәнді болады, егер және тек қана V жиынынан E жиынына инъекция болса, ол E жиынынан V жиынына биекцияны тудырса.
In his original paper, Rosa proved that all Eulerian graphs with size equivalent to 1 or 2 (mod 4) are not graceful. Whether or not certain families of graphs are graceful is an area of graph theory under extensive study. Arguably, the largest unproven conjecture in graph labeling is the Ringel–Kotzig conjecture, which hypothesizes that all trees are graceful. This has been proven for all paths, caterpillars, and many other infinite families of trees. Anton Kotzig himself has called the effort to prove the conjecture a "disease".
Өз бастапқы мақаласында Роза графтың өлшемі 1 немесе 2 (4-ке бөлінгенде қалдық) тең болатын барлық Эйлер графтары сәнді бола алмайтынын дәлелдеді. Графтардың белгілі бір отбасыларының сәнді болуы немесе болмауы граф теориясының кеңінен зерттелетін саласы болып табылады. Графтарды нөмірлеудегі ең үлкен дәлелденбеген болжам – барлық ағаштар сәнді деген Рингель-Котциг болжамы. Бұл барлық жолдар, гусеницалар және көптеген басқа да шексіз ағаш отбасылары үшін дәлелденді. Антон Котцигтің өзі осы болжамды дәлелдеуге жасалған тырасты "ауру" деп атады.
In his original paper, Rosa proved that all Eulerian graphs with size equivalent to 1 or 2 (mod 4) are not graceful. Whether or not certain families of graphs are graceful is an area of graph theory under extensive study. Arguably, the largest unproven conjecture in graph labeling is the Ringel–Kotzig conjecture, which hypothesizes that all trees are graceful. This has been proven for all paths, caterpillars, and many other infinite families of trees. Anton Kotzig himself has called the effort to prove the conjecture a "disease".
Гармониялық таңбалау
G графигіндегі "гармониялық белгілеу" – G төбелерінен k модулі бойынша бүтін сандар тобына инъекция, мұнда k – G қабырғаларының саны, және бұл G қабырғалары мен k модулі бойынша сандар арасындағы биекцияны тудырады. Бұл (x, y) қабырғасы үшін қабырғалық белгіні екі төбе x және y белгілерінің қосындысы ретінде (mod k) қарастыру арқылы жүзеге асырылады. "Гармониялық граф" – гармониялық белгілеуі бар граф. Жұп емес циклдар гармониялық, сондай-ақ Петерсен графтары да. Егер бір төбелік белгіні қайта пайдалануға рұқсат берілсе, ағаштардың барлығы гармониялық деп болжанады. Жеті беттік кітап графтары гармониялық емес графтардың мысалы болып табылады.
Графикті бояу
Графикті бояу – график белгілеулерінің кіші класы. Төбелерді бояу көршілес төбелерге әртүрлі белгілер тағайындайды, ал қабырғаларды бояу көршілес қабырғаларға әртүрлі белгілер тағайындайды.
Бақытты таңбалау
Граф G-дің сәтті таңбалануы — G төбелеріне оң бүтін сандарды тағайындау, мұнда егер S(v) v төбесінің көршілеріндегі таңбалардың қосындысын білдірсе, онда S — G төбелерінің бояуы болады. G-дің "сәтті саны" — G-нің {1, ..., k} бүтін сандарымен сәтті таңбалануы бар ең кіші k саны.