ГРАФТАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 53 бет
Таңдаулыға:

МАЗМҰНЫ

КІРІСПЕ . . . 3

1 ГРАФТАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ . . . 8

Графтар теориясының негізгі ұғымдары және анықтамалары . . . 8
Графтардың берілу тәсілдері, сандық сипаттамалары . . . …… . . . 14
Эйлерлік және гамильтондық графтар . . . 18

1. 4 Графтардағы қысқа жолды табу. Дейкстр алгоритмі . . . 28

2 ҚОЛДАНБАЛЫ ЕСЕПТЕРДІ ШЕШУДЕ ГРАФТАРДЫ ҚОЛДАНУ . . . 33

2. 1 Коммивояжер есебін «Тармақ және шекара» әдісімен шешу . . . . 33

2. 2 Желілік қойылымдағы көлік есебін шешу. Потенциалдар әдісі . . . . . 35

2. 3 Желілік жоспарлауда графтардың қолданылуы . . . 41

2. 4 Графтар қолданылып шығарылатын экономикалық есептер . . . 41

ҚОРЫТЫНДЫ . . . 62

ҚОЛДАНЫЛҒАН ДЕРЕКТЕР ТІЗІМІ . . . 64

МАЗМҰНЫКІРІСПЕ . . . 31 ГРАФТАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ. . . 8Графтар теориясының негізгі ұғымдары және анықтамалары . . . 8Графтардың берілу тәсілдері, сандық сипаттамалары . . . …… . . . 14Эйлерлік және гамильтондық графтар . . . 181. 4 Графтардағы қысқа жолды табу. Дейкстр алгоритмі . . . 282 ҚОЛДАНБАЛЫ ЕСЕПТЕРДІ ШЕШУДЕ ГРАФТАРДЫ ҚОЛДАНУ. . . 332. 1 Коммивояжер есебін «Тармақ және шекара» әдісімен шешу . . . . 332. 2 Желілік қойылымдағы көлік есебін шешу. Потенциалдар әдісі . . . . . 352. 3 Желілік жоспарлауда графтардың қолданылуы . . . 412. 4 Графтар қолданылып шығарылатын экономикалық есептер . . . 41ҚОРЫТЫНДЫ . . . 62ҚОЛДАНЫЛҒАН ДЕРЕКТЕР ТІЗІМІ . . . 64:

КІРІСПЕ

Графтар теориясы XVIII ғасырдың 30-шы жылдарының ортасында математиканың өз алдына бір саласы ретінде басталып, осы уақытқа дейін қарқынды дамып келе жатқан ғылым.

Графтар теориясы объектілерді реттеудің моделін құрып, әр түрлі саладағы есептерді жалпылау және шешімін табуда қолданылатын қарапайым, тиімді және қуатты құрал болып табылады. Жеке жағдайда, мұндай есептерге байланыс желілерін зерттеу және жобалау, электрлік желілерді талдау, баспа схемаларын талдау, электрлік және монтаждау схемаларын жобалау есептері, бағдарламалардың блок-схемалары, автоматтарды зерттеу, календарлық жоспарлау есептері, материалдық-техникалық жабдықтауды қамтамасыз ету және жоспарлау, ақпараттарды іздеу, ақпараттар теориясы, коммуналдық қызмет көрсету мекемелерін орналастыру, ойындар теориясы, биология, генеалогия, бас қатырғыш ойындар, заттың химиялық құрамын анықтау, экономикалық есептердің алуан түрлері және басқалар жатады.

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

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

Немесе, берілген нүктелерді бір-бірімен қосатын сызықтар тобы граф деп аталады. Берілген нүктелерді графтың төбелері дейді де, төбелерді екі-екіден қосатын сызықтарды графтың қабырғалары дейді. Қабырға немесе қыр түзу де, қисық сызық та болуы мүмкін. Мысалы, Алматы, Көкшетау, Семей, Талдықорған қалаларын алайық, оларды қысқаша А, К, С, Т әріптерімен белгілейік. Сонда Алматы-Семей жолы АС, Көкшетау-Талдықорған жолы КТ, . . . , т. с. с. болады (темір жол, қара жол, су жолы, әуе жолы-бәрібір) . Бұл жолдардың схемасы граф құрастырады, схемадағы А, К, С, Т нүктелері графтың төбелері АС, АК, . . . , СТ сызықтары графтың қабырғалары рөлін атқарады. Мұндай графтың төбелері үшінші дәрежелі болады. Төбелері сызықтар арқылы қосылмаған толымсыз графтар да кездеседі. Оларды жетпей тұрған қабырғаларын сызып, толықтыруға болады.

Төбелері бір жазықтықта жататын графтар жазық графтар болып табылады, төбелері бір жазықтықта жатпайтын графтар кеңістік графтары болады.

Кеңістік графтарын жазық графтарға жіктеуге болады. Әдетте жазық графтар қабырғалары төбелерде ғана қиылысатындай етіліп сызылады. Графтардың алдын-ала берілген шарттарды қанағаттандыратын арнайы түрлері де бар. Мысалы, бағдарлы графтарда қабырғаларының бағдары - төбелерден өту реті бойынша айтылады, қабырғаларының «салмағы» бар графтарда тиісті қабырғаларының ұзындығы, өткізу қабілеті т. с. с. көрсетіледі. Кейбір қабырғалары бірнеше рет есептелетін («еселі қабырғалар»), кейбір төбелері айрықша рөл атқаратын («полюстер») графтар да қарастырылады.

Граф ұғымының орнына “желі” ұғымы жиі қолданылады.

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

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

Күрделі комплексті жұмыстар моделі біздің ғасырымыздың 50-ші жылдарында жинақталып іске қосылып, қолданыла бастады. Америкада желілік модель американ әскери-теңіз флотының су асты қайықтарына жарық беріп тұратын “Поларис” деп аталатын баллистикалық ракетаны жасау барысында қолданылды. Жұмыс Американың 48 штатында 6000 фирманың қатысуымен орындалды, желілік график құрамында 1 оқиға болды. АҚШ-та желілік жоспарлау және басқару әдісі кең қолданылады, алғаш шыққан және кең қолданыс тапқан басқару жүйесі “ПЕРТ” деп аталады. “ПЕРТ” жүйесін игермеген бірде-бір фирма контракт ала алмайтын болған. Америкалық экономистер пікірінше графтар теориясын қолдана отырып құрылған желілік модельдеу жұмыстар комплексінің орындалу ұзақтығын үш есеге дейін қысқартуға мүмкіндік береді.

Біздің елімізде желілік жоспарлау және басқару деп аталатын бірнеше жүйе бар. Бұл жүйелер негізі де желілік график болып табылады. ЖЖБ көмегімен ТМД елдеріндегі ірі-ірі құрылыс жұмыстары, алып заводтар, ЖЭЦ т. б. салынды. Қазіргі жағдайда да мекемелер, құрылыс фирмалары, ғылыми зерттеу, жобалау институттары т. б. осы жүйе бойынша жұмыс жасайды. Желілік графиктің немесе оның бөліктерінің көрнектілігі жалпы жүйенің болмысын, барлық жұмыстардың бір-бірімен байланысын қабылдауды жеңілдетеді, жобаны іске асыру барысындағы жұмыстар процесін қысқартуға көмектеседі.

Бұл зерттеу жұмысында қарастырылатын графтардағы экстремалды есептерді шешу әдістері графтар теориясының негізгі классикалық есептерінің бірі болып табылады. Графтардағы экстремалды есептер дегеніміз - желіде қандай да бір граф арқылы берілген сандық функцияның ізделінді ең үлкен немесе ең кіші мәнін табу есептері болып табылады. Мұндай есептерге қысқа жолды іздеу есептері, тағайындау есептері, коммивояжер есебі, желідегі максимал ағынды есептеу, тұйық сызықты ажырату есебі секілді есептерді жатқызуға болады.

Бүгінде бұл есептерді шешудің көптеген алгоритмдері белгілі.

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

Графтағы экстремалды есептер бағытталған, бағытталмаған немесе аралас графтар үшін анықталуы мүмкін. Жұмыста қарапайым түрде бағытталмаған граф үшін есептің қойылуы қарастырылады.

Зерттеу жұмысы тақырыбының өзектілігі - жұмыста негізі қарапайым идеялар мен элементтер: нүкте, оларды қосатын сызықтар бола тұрып, олардан көлемді, күрделі формалар тұрғызып және ол формаларды қызықты қасиеттері бар формаға, күрделі жобаға айналдыратын графтар теориясының жұмыс принциптеріне түсінік беріледі, бұл теория өз алдына жеке теория болғанымен ғылым мен математиканың басқа салаларымен тығыз байланыста екендігі, қоғам мүшелерінің күнделікті жұмыс жоспарларын, жалпы өмірлік идеясын құру, іске асыру барысында осы теория элементтерін қолдануға болатындығы көрсетіледі. Компьютерлік жүйелерді, телефон байланысын, тұрбалар жүргізу және жол құрылысын жобалау т. б. жұмыстарында шығынды, жұмсалатын қаржыны минималдау қажеттілігі туындайды. Осыған байланысты аз ұзындықтағы маршрутты, жолды анықтау есебі туындайды. Бұл есеп қай кезде де өзекті мәселе болып табылады және оны шешуде әртүрлі әдістер қолданылады. Жұмыста графтардағы экстремалды есептердің қойылуы, есептердің оңтайлы шешімдерін табудың Дейкстр (2), Форд-Фалкерсон, Литлл алгоритмдері баяндалып, оларды практикада қолданылуы есептер көмегімен түсіндіріледі.

Графтар теориясын олардың негізгі ұғымдары мен анықтамаларын, геометриялық кескінделуін, графтарды беруде қолданылатын матрицаларды, графтардың қасиеттерін білмей, қолданылу жағдайларын қарастырмай оқып-үйрену мүмкін емес. Сондықтан да диссертация жұмысы барысында жүргізілген зерттеу мақсаты - графтар теориясының негізгі ұғымдарын, анықтамалары мен теоремаларын талдап, зерттей келе қолданалы есептерді шешуде графтардың қолданылуымен, графтар теориясының әдістерімен танысу және оларды практикада қолдана білу болып табылады. Сонымен қатар, графтар теориясында қолданылатын матрицалар түрлеріне түсінік беру, графтарды ЭЕМ-да беруге қолайлы болатын матрицалар түрінде кескіндеу болып табылады.

Диссертация жұмысының зерттеу пәні және нысаны - соңғы жылдарда қарқынды дамып, математикалық кибернетиканың негізіне айналған, қолданбалы математиканың бөлімі болып табылатын дискретті математика пәнінің нысандарының бірі - графтар теориясының негізгі ұғымы - граф, графтардағы ара қашықтық, қысқа жол, оны іздеу есебі, коммивояжер есебінің оңтайлы шешімдерін табу жолдары, транспорттық есептердегі максимал ағындарды есептеу мәселелері болып табылады.

Зерттеу міндеттері :

а) Дискретті математика пәні және оның бөлімдерімен танысу;

ә) Графтар теориясының негізгі нысаны, анықтама, теоремаларымен, пайда болу тарихымен танысу, оқып-үйрену;

б) Графтартың қолданбалы есептерді шешуде қолданылу әдістерімен танысу және оларды практикада қолдана білу.

Зерттеудің әдістемелік негізіне Қазақстан Республикасындағы 2011-2020 жылдарға арналған білім беруді дамытудың мемлекеттік бағдарламасы, қазіргі кезеңдегі оқыту әдістемесі және математика ғылымдарының жетістіктері, дидактиканың оқыту ұстанымдары, отандық және шетелдік математик ғалымдардың оқыту нәтижесінде білім алушының ақыл-ой, танымдық қабілеттерін дамыту туралы іргелі теориялық қағидалары, мамандыққа сәйкес білім берудің мемлекеттік стандарты, бағдарламалар, оқулықтар, оқу құралдары, оқытудың жаңа технологиялары туралы ғылыми-әдістемелік еңбектер негіз болды.

Зерттеудің теориялық негіздерін шетелдік және отандық Джеймс Андерсон, Судоплатов С. В., Овчиникова Е. В., Нефедов В. Н., Осипова В. А., Горбатов В. А., Березина Л. Ю., Джумадильдаев А. С., Қ. Жетпісов., Г. И. Салғараева., Алексеев В. Е., Таланов В. А. тәрізді белгілі ғалымдардың дискретті математика, графтар теориясы саласындағы еңбектері құрайды.

Мәселенің зерттелу деңгейі - графтар теориясының математикалық пән болып қалыптасуы Эйлердің 1736 жылғы Кенигсберг көпірлері туралы әйгілі тұжырымдамасынан бастау алған, алайда бұл мақала одан кейінгі жүз жыл бойына жалғыз ғана мақала болып есептелді. Графтар теориясы өткен ғасырдың орта шамасында жаратылыстану ғылымдарының (физика, электротехника, химия, биология) және бас қатыру ойындары әсерінен Англияда қайта жаңғырды. Олардың ішіндегі ең маңыздысы 1850 жылдары де-Морганның графтарды бояу, төрт бояу есебі. Соңғы кезде графтар теориясы білім-ғылымның әртүрлі саласы мамандарының қызығушылығын туындатып отыр. Графтардың дәстүрлі физика, химия, биология саласындағы қолданылуларымен қатар, оның экономикада, әлеуметтануда, лингвистикада, топологияда, топтар теориясында, ықтималдықтар теориясында, психологияда да қолданылатындығы белгілі болды. Графтар теориясы элементтері мен қазіргі уақытта қарқынды дамып отырған теориялық кибернетика (автоматтар теориясы, амалдарды зерттеу, кодтау теориясы, ойындар теориясы, бағдарламалау) арасындағы байланыс өте маңызды орын алады.

Графтар теориясының, жалпы дискретті математика курсының негізін қалаған, қазіргі дискретті математика саласына қомақты үлес қосқан ағылшын математигі, философ Б. Рассел, ағылшын математигі А. Тьюринг, америкалық математиктер А. Чёрч, К. Гёдель, Э. Пост, С. Клини, Дж. Андерсон, польшалық математиктер Л. Лукасевич, С. Мостовской, совет математиктері А. А. Марков, И. И. Жегалкин, П. С. Новиков, В. М. Глушков, Нефедов В. Н., Осипова В. А. ресейлік ғалымдар С. В. Яблонский, О. Б. Лупанов, Ю. И. Журавлев, О. Оре, О. И. Мельников есімдерін атауға болады.

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

Ғылыми жаңашылдығы. Студенттердің дүниетанымын кеңейтуге, логикалық ойлау мәдениетін дамытуға игі әсер ететін дискретті математиканың және оның негізгі тарауларының бірі графтар теориясының негізгі анықтама, теоремалары, қазіргі замандағы қолданылу жағдайлары, графтар теориясының қолданбалы есептерді шешуде қолданылуы көрсетілді, қысқа жолды іздеуде Дейкстр алгоритмі, коммивояжер есебін шешуде, желілік жоспарлауда, көлік есебін шешуде графтардың қолданылуы көрсетілді.

Диссертация жұмысының теориялық маңыздылығы - теориялық кибернетика саласы бойынша білім алушылар мен мамандар үшін графтар теориясының маңызды мәселелерінің бірі болатын графтардағы экcтремалды есептердің қойылуымен, есептің теориялық және практикалық тұрғыдан жүйелі түрде баяндалуымен анықталады.

Диссертация жұмысының практикалық маңыздылығы - графтар теориясы программалау теориясында, есептегіш машиналар жасауда, физикалық, химиялық және технологиялық процестерді зерттеуде, лингвистикада, халық шаруашылығын жоспарлау сияқты алуан түрлі жұмыстарда қолданылады. Олай болса, әрбір жас заман ағымына сай жан-жақты дамыған, білімді, білікті азамат боламын десе, қарапайым идеялар негізінде үлкен игі істерге бастайтын графтар теориясынан және оның негізгі классикалық есептерінің бірі болып табылатын графтардағы экстремалды есептердің қойылу жағдайларынан, қолданбалы есептерді шешуде графтардың қолданылуынан, сонымен қатар олардың қолданбалы мүмкіндігінен хабары болғаны дұрыс.

Диссертация жұмысының құрылымы. Жұмыс кіріспеден, 2 бөлімнен, қорытынды және пайдаланылған деректер тізімінен тұрады.

1 ГРАФТАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ

Графтар теориясының негізгі ұғымдары және анықтамалары

Ресейдің батысында Калининград қаласы бар, бұрын ол Кенигсберг деп аталды. Қала арқылы Преголь өзені ағып өтеді. Ол екі жеңге бөлінеді және аралды айналып өтеді. XVIII ғасырда қалада 1-суретте көрсетілгендей орналасқан жеті көпір болды.

Старинная карта Кёнигсберга. Буквами обозначены части города: А — Альтштадт, Б — Кнайпхоф, В — Ломзе, Г — Форштадт. Цифрами обозначены мосты (в порядке строительства): 1 — Лавочный, 2 — Зелёный, 3 — Рабочий, 4 — Кузнечный, 5 — Деревянный, 6 — Высокий, 7 — Медовый

1-сурет. Кеннигсберг

Бір күні қала тұрғыны өзінің танысынан барлық көпірлерден олардың әрқайсысында тек бір рет болып, серуендеу басталған жерге оралатындай етіп өте алады ма деп сұрады. Көптеген қалалықтар бұл міндетті қызықтырды, алайда ешкім шешім қабылдай алмады. Бұл мәселе түрлі ел ғалымдарының назарын аударды. Бұл мәселені белгілі математик Леонард Эйлер шешеді. Сонымен қатар, ол осы нақты міндетті шешіп қана қоймай, сондай-ақ осындай міндеттерді шешудің жалпы әдісін ойлап тапты. Сондықтан графтар теориясының негізін қалаушы Леонард Эйлер деп саналады.

Көптеген қолданбалы есептерде түрлі объектілер арасындағы байланыс жүйелері зерттеледі. Объектілер төбелер деп аталады және нүктелер немесе дөңгелекшелермен белгіленеді, ал төбелер арасындағы байланыстар нүктелердің жұптарын қосатын кесінділермен белгіленеді; және бұл кесінділер қабырғалар деп аталады. Мұндай жүйелерді қарастыру граф ұғымына әкеледі.

V - бос емес жиын, - осы жиынның екі элементтен тұратын барлық ішкі жиыны, яғни, , егер болсын.

Анықтама. G= жұбы бағытталмаған граф ( немесе граф) деп аталады. Мұндағы .

V жиынының элементтері графтың төбелері деп аталады, ал E жиынының элементтері графтың қабырғалары деп аталады.

Графтардың E, V әріптермен белгілену себебі ағылшын сөздерінің бас әріптерінен алынған. Яғни vertex- төбе, edge- қабырға деген мағыналарды білдіреді екен.

1-мысал. Келесі графты қарастырайық.

1-сурет. Графтың мысалы

Мұндағы төбелер жиыны болады, ал қабырғалар жиыны болады. Мұнда

Анықтама. Егер е қабырғасы төбелерін қосатын болса, яғни онда төбелері іргелес деп аталады, ал қабарғасы төбелеріне инцидентті деп аталады.

Анықтама. Егер V және E жиындары ақырлы болса, онда G ақырлы граф деп аталады.

Егер е қабырғасы төбелеріне инцидентті болса, онда мұндай төбелер е қабырғасының шекаралық нүктелері деп аталады.

Егер төбелері е қабырғасына инцидентті болса және төбесі төбесінмен беттессе, яғни қабырғаның басы мен соңы бір төбеде орналасса, онда е қабырғасы ілмек деп аталады. Бұл жағдайда төбесі өз-өзіне ірелес болып табылады. 1-суреттегі қабырғасы ілмекке мысал болады.

төбелері біруақытта қабырғаларына инцидентті болса, онда қабырғалары параллель қабырғалар деп аталады.

Егер қабырғаларының ең болмағанда бір шекаралық нүктесі болса, онда қабырғалары іргелес деп аталады.

Іргелестік - екі ұқсас элементтің арсындағы қатынас ( төбелер арасындағы немес қабырғалар арасындағы) болып табылады. Инциденттік - әртүрлі элемент арасындағы қатынасты қатынасты көрсетеді.

2-мысал. Келесі графты қарастырайық.

2-сурет.

Суреттегі графта көріп отырғанымыздай, және қабырғалары параллель болады, және қабырғалары сыбайлас болып табылады. және , және сыбайлас қабырғалар бола алмайды, қабырғалы ілмек болып табылады.

Анықтама. V төбесіне инцидентті қабырғалар саны (ілмек екі рет есептеледі) V төбесінің дәрежесі деп аталады және деп белгіленеді. Егер болса, V төбесі оқшауланған болып саналады. Егер қабарға ілмек болатын болса, онда төбесінің дәрежесі болады.

3-мысал. Граф төбелерінің дәрежелерін табайық.

3- сурет.

Анықтама. Графтың барлық төбесі оқшауланған болса, онда граф ерекше (бос) деп аталады.

4 - мысал. Ерекше графқа мысал қарастырайық.

4 - сурет. Ерекше граф.

G= ( V, E ) және графтарды қарастырайық және биекциясы ( өзара бірмәнді бейнелеу) бар болсын.

Анықтама. Егер G графының кез-келген және төбелері үшін олардың және бейнелері графында сыбайлас болады, сонда, тек сонда ғана және төбелері G графында сыбайлас болса. Бұл биекция G графының графы үшін изорморфизмі деп аталады. Егер осындай биекция бар болатын болса, онда G графы графына изоморфты болады.

5 - мысал. Изоморфты графтарға мысал келтірейік.

5 - сурет. Изоморфты графтар

6 - сурет. Изоморфты емес графтар.

G және графтарындағы төбелер саны бірдей, бірақ төбелердің дәрежелері әртүрлі. Мысалы, G графындағы төбесінің дәрежесі бірге тең. графында дәрежесі екіден кем болатын төбе жоқ.

Теорема. Ақырлы графта тақ дәрежелі төбелердің саны жұп болады.

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

G= ( V, E ) ақырлы графты қарастырайық. және сәйкесінше төбелердің және қабырғалардың саны болсын.

- таңбасы жиынның қуатын білдіреді, яғни жиындағы элементтер санын білдіреді.

Тұжырым:

V төбелер жиынын екі жиынға бөлейік:

- жұп дәрежелі төбелердің жиыны, - дәрежелері жұп болатын төбелердің дәрежелерінің қосындысы.

- тақ дәрежелі төбелердің жиыны, - дәрежелері тақ болатын төбелердің дәрежелерінің қосындысы.

тұжырымы бойындша, бұл қосынды жұп болады. қосындысы да жұп болады.

- жұп сандардың қосындысы жұп болғандықтан, қосынды жұп болады.

қосындысында тақ сандар бір-біріне қосылады. қосындысы жұп болу үшін қосылғыштардың саны жұп болу керек. Дәрежесі тақ болатын төелердің саны жұп болады.

Анықтама. Кез келген екі төбесі сыбайлас болатын графты толық граф (ілмексіз) деп атайды. n төбеден тұратын толық графтың қабырғасы болады.

Комбинаторикада - n элементтен k терулер санын білдіреді. Терулер саны келесі формуламен анықталады:

Cонда, - ні былайша есептейміз:

Анықтама. Граф толық (ілмекпен) деп аталады, егер кез-келген екі төбесі сыбайлас болса, сонымен қатар әрбір төбеде ілмек болса. Мұндай графтардағы қабырғалар санын қайталанатын терулер формуласымен есептейміз, яғни қабырға.

Анықтама. графы графының ішкі графы деп аталады, егер төмендегі екі шарт орындалса:

2. Егер қабырғасы және қабырғаларына инцидентті болса, онда қабырғасыда қабырғаларына да инцидентті болады.

Маршруттар, жолдар, циклдер

Анықтама. графының қабырғаларының ақырлы тізбегі ұзындығы n- ге тең маршрут деп аталады, егер төбелеріне қабырғасы инцидентті болатын төбелер тізбегі бар болса. Егер болса, онда маршрут тұйық деп аталады.

Анықтама. Барлық қабырғалары әртүрлі болатын маршрутты жол деп атайды. Тұйық жол - цикл деп аталады. Қарапайым тұйық жол - қарапайым цикл деп атайды.

Байланыс

Анықтама. Егер графтағы кез-келген төбелердің жұбы кем дегенде бір тізбекпен байланысқан болса, онда мұндай графты байланысқан граф деп атайды. Қарама-қарсы жағдайда байланыспаған граф деп аталады.

7 - мысал.