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

График теориясының пайда болу және даму тарихы 1736 ж., Леонгард Эйлер, Конигсберг көпірлері мәселесі бір рет?) o 19 ғасырдың ортасы. , Г.Кирхгофтың электр тізбегінің графиктерін пайдаланып сипаттауы, А.Кейли химиялық схемалар o 30-жылдардың ортасында математикалық пән қалай қалыптасты. 20 ғасыр (1936, басылым о

Графтар теориясын қолдану салалары o o o Электрлік және басқа тізбектер мен жүйелерді талдау және синтездеу, желіні жоспарлау және басқару, операциялық зерттеулер, желілердегі оңтайлы маршруттар мен ағындарды таңдау, организмдердің тіршілік әрекетін модельдеу, кездейсоқ процестерді зерттеу және т.б. Шешімі объектілерді және олардың арасындағы байланыстарды жинақтаумен шектелетін практикалық есептер. Мысалы, жол картасы – елді мекендер арасындағы байланыс, адамдар, оқиғалар, мемлекеттер, жалпы кез келген объектілер арасындағы әртүрлі байланыстар мен қатынастар ретінде көптеген басқатырғыштар мен ойындар.

o Жолдарды үзбей немесе қайталамай белгілі бір пішінді салуды талап ететін басқатырғыштар, мысалы, Магометтің қылыштары

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

Графиктердің мысалдары o o Кеңістіктегі кез келген көпбұрыштың жақтауы Метродағы сызықтардың схемасы Құрылымдық формулаларМолекулалардың отбасы ағашы

Графиктердің көмегімен шешілген есептердің мысалдары 1. Саяхатшылар o Туристік кеңсе С, Г, Е, F, G қалаларында орналасқан барлық көрікті жерлерді аралай отырып, А қаласынан В қаласына саяхаттағысы келетін саяхатшыларға маршрут жасайды. Жолда H, K, M. Туристер барлық көрсетілген қалаларды аралайтындай және олардың әрқайсысына тура бір рет баратындай етіп саяхат маршрутын жасау керек.

o Мәселенің шарты бойынша жол А нүктесінен басталып, В нүктесінде аяқталуы керек. D және F қалаларына апаратын тек екі жол бар екенін ескеріңіз. Сондықтан саяхатшылар бұл жолдармен міндетті түрде өтеді. Оларды жуан сызықтармен белгілейік. Бұл CDEFG маршрут сегментін анықтайды. Бұл туристер AE, AG, EM жолдарынан өтпейді деген сөз (әйтпесе Е нүктесіне екі рет барады). Осы жолдарды кесіп өтейік. Ауыр сызықты AC учаскесін белгілейік, өйткені А-дан тек осы жол қалады. CM-ді сызып тастаймыз (біз С-де болдық). Екі жол MH арқылы кесілмей қалды: MH және MB, яғни туристер олармен жүреді. Оларды жуан сызықтармен белгілейік. Жалғыз жол - G-ден H-ға жету

o Осылайша біз дұрыс жолды таптық. Бұл жерде бізге қалалар мен жолдардың орналасуы көмектесті, бұл шын мәнінде 10 шыңы мен 17 жиегі бар график. A, D, F төбелері екінші дәрежелі, C және K төбелері үшінші дәрежелі, H, M, B төбелері төртінші дәрежелі, G және E төбелері бес дәрежелі.

2. Таныстар o 8 адамнан тұратын компанияда барлығы тағы екі адамды таниды ма?

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

3. Шахмат турнирі o Турнирге n шахматшы қатыссын, барлығы бір-бірімен тура бір ойын ойнауы керек. Әрбір қатысушыны графиктің төбесімен байланыстырыңыз және әрқайсысы сәйкес шыңдарды қосатын графтың жиегімен ойын ойнады.

Толық график o o o Турнир басталар алдында график тек ұпайлардан тұрады, оның шеттері жоқ. Мұндай графиктер нөлдік графиктер деп аталады.Турнирдің соңында әрбір қатысушы кез келген басқалармен ойнады және әр жұп шыңдар жиекпен біріктірілген. Мұндай график толық деп аталады. n шыңы бар толық графикте әрбір төбенің дәрежесі (n-1) Толық емес графты жетіспейтін жиектерді қосу арқылы толық жасауға болады. Суретте. қалың сызықта 5 шыңы бар график көрсетілген, ол толық емес. Қосу арқылы

Бағдарланған граф o o o Көбінесе объектілер арасындағы байланыстар белгілі бір бағдармен сипатталады (бір жақты қозғалыстағы жолдар схемасы, адамдар арасындағы қарым-қатынастағы бағыныштылық немесе үлкендік, спорттық жарыстардағы командалар арасындағы кездесулердің нәтижелері) Шахмат турнирінің графигі біз бейнелеген әр ойында кім жеңгені туралы ақпарат бермейді. А төбесінен В шыңына дейін әр жиекке көрсеткі қоюға болады, егер А шахматшысы В шахматшысынан жеңіліп қалса, яғни оларға бағытты көрсету арқылы жиектерді бағдарлаңыз.Әр жиектің бағыты көрсетілген график деп аталады.

o Бағытталған және бағытталмаған жиектері бар график аралас деп аталады (мысалы, кейбір ойындар тең аяқталған шахмат турнирінің графигі. Жебесіз жиекті тең нәтижемен салыстырамыз)

Графиктің жолы o o o Ерікті графтағы ұзындығы m жол дегеніміз көршілес екі шеттің шекаралық төбелері сәйкес келетін m жиектер тізбегі (міндетті түрде ерекше емес). Маршруттың ұзындығы - жиектер саны (егер біз жиек бойымен 2 рет жүрсек, онда бұл жиекті 2 рет санаймыз) Егер оның бастапқы және соңғы шыңдары бірдей болса, жол жабылады Тізбек - барлық жиектері болатын ашық маршрут әр түрлі Қарапайым тізбек – барлық шыңдары әртүрлі болатын тізбек (мысал – 1 тапсырма. (саяхатшылар туралы)

Циклдер, байланысқан графиктер o o o Цикл – барлық жиектері бөлек болатын тұйық жол. Қарапайым цикл - барлық шыңдары әртүрлі болатын цикл (мысалы, танысу мәселесі. Бірінші графикте бір қарапайым цикл бар, екіншісі және үшіншісі әрқайсысында екі қарапайым цикл бар) Кез келген нүктеден маршрут болса, граф байланысты деп аталады. оның төбелерінің кез келген басқасына, және басқаша ажыратылған (мысалы, таныстар мәселесі, бірінші график қосылған, әр адам өзінің таныстары арқылы таныса алады, екінші және үшінші ажыратылған, олар компанияда қалады бейтаныс адамдар)

o o o o B-D-A-C-D-A - ашық маршрут A-C-D-A-B-D-A- жабық маршрут A-C-D-E-F-D-B - A-B-G-H тізбегі– қарапайым тізбек A-C-D-E-F-D-A – D-E-F-D циклі– қарапайым цикл Осы маршруттардың ұзындығын есептеңіз, олардың қандай түрі екенін анықтаңыз A-B-D-F-E-D-C-A бағыттары; A-D-E; D-E-F-D; A-C-D-B-A;

Ағаштар o o Ағаш - циклдері жоқ байланыстырылған график Генеалогиялық ағаш, файлдық жүйе және т.б.

Тапсырма 4. Бөлшектерге бөлу o Қағаз парағын 3 бөлікке кесіңіз. Алынған жапырақтардың бір бөлігі қайтадан 3 бөлікке кесіледі. Кесілген жапырақтардың бір бөлігі - қайтадан үш бөлікке және т.б. К кесілген болса, қанша жеке жапырақ алынады?

Тапсырма 4. Бөлу (шешім) o o Қағаз графасының үстіңгі парақтары. Толтырылған шыңдар кесілген жапырақтарға, толтырылмағандар кесілмегендерге сәйкес келеді. Бір жапырақты кескенде жапырақ саны 2-ге артады.Егер барлығы к жапырақ кесілген болса, онда жапырақ саны 2к-ға артады. Бастапқыда бізде бір парақ болды. , сондықтан k кесілгеннен кейін сіз (2 к+1) жапырақтар аласыз. График k=6 болған жағдайды көрсетеді. (2к+1)=13

Графиктің төбелерінің градустарының қосындысы туралы теорема o o Г графының N төбесі және M қыры болсын. Әрбір i-ші төбенің di дәрежесі бар Әрбір жиек екі төбені байланыстыратындықтан, ол графиктің төбелерінің градустарының қосындысына екі қосады, сондықтан төбелердің градустарының қосындысы жиектер санының екі еселенгеніне тең.

Есеп 5. Жолдар саны o Әр қаладан дәл 3 жол шығатын мемлекетте дәл 100 жол болуы мүмкін бе?

Тапсырма 5. Жолдар саны (шешім) o Мұндай жағдай болуы мүмкін делік. Штатта N қала бар, әр қаладан 3 жол шығады. Сонымен, бізде N төбелері бар граф бар, олардың әрқайсысының 3 дәрежесі бар. Демек, төбелердің градустарының қосындысы 3 N, ал шеттерінің саны 3 N/2. Бұл сан шартты түрде 100-ге тең. Яғни, 3 N / 2 \u003d 100 немесе 3 N \u003d 200. Мұндай натурал сан жоқ. Бұл штатта 100 жол болуы мүмкін емес деген сөз.

Дербес o Белгілі бір патшалықта патша жарлық шығарды: 7 қала салып, әр қаладан 3 жол шығатындай етіп оларды жолдармен байланыстыр. Осы тәртіпті орындаймыз ба? Әр қаладан шығатын 4 жол болса, орындала ма?

Есеп 6. Кенигсберг көпірлері туралы o Кенигсберг қаласы Прегель өзенінің жағасында, 7 көпірден тұратын қалада орналасқан. Әр көпірден бір-ақ рет өтіп, үйден шығып, қайта оралу үшін серуендеуге бола ма?

Кенигсберг көпірлері есебін шешу o o o Қаланың A, B, C, D бөліктерін белгіле. Бұл графиктің төбелері болады. Қаланың бөліктерін байланыстыратын көпірлер - графиктің шеттері. Эйлер есептің шешімі жоқ екенін көрсетті, яғни барлық шеттерден дәл бір рет өтетін цикл жоқ. Ақыр соңында, егер мұндай цикл болған болса, онда графтың әрбір шыңында қанша шеттен шығатын болса, сонша шеттер кіретін еді, яғни графтың әрбір төбесінде шеттердің жұп саны болады (бар төбеге бір жиегімен кірген болса, біз одан басқа жиегімен шығуымыз керек). Дегенмен, бұл шарт Кенигсберг картасын көрсететін график үшін қанағаттандырылмағаны анық. Графиктің әрбір шыңының дәрежесін анықтау арқылы мұны тексеріңіз

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

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

Өз бетіңізше o Бұл графиктер Эйлер графы екенін анықтаңыз? (жолдарды үзбей немесе қайталамай, оларды бір рет қаламмен айналдырып, біз бастаған нүктеге оралуға болады ма) Егер иә болса, олардан Эйлер циклдерін табыңыз (мұны қалай жасау керектігін көрсетіңіз)

Эйлер жолы o o Эйлер жолы – барлық шеттері бір рет өтетін, бірақ бастапқы нүктеге оралмайтын жол. Егер графикте Эйлер циклі болмаса, онда Эйлер жолын табу мәселесін қоюға болады.

Эйлер жолының болуының жеткілікті шарты o o Егер Г графигінде А және В ұштары бар Эйлер жолы болса (А В-мен сәйкес келмейді), онда Г графигі қосылған және А және В оның жалғыз тақ төбелері. Шынында да, графиктің байланысы Эйлер жолының анықтамасынан туындайды. Егер жол А нүктесінен басталып, басқа В шыңында аяқталса, онда жол А және В арқылы қайта-қайта өткен болса да, А және В екеуі де тақ болады. Жол графиктің кез келген басқа шыңына және одан шығуы керек еді, яғни барлық қалған шыңдары жұп болуы керек.

Эйлер жолының болуының қажетті шарты o o Керісінше де дұрыс: егер G графы қосылған болса және А және В оның жалғыз тақ төбелері болса, онда G графигінде А және В ұштары бар Эйлер жолы болады. А және В төбелері. графиктің жиегі арқылы қосылуы мүмкін немесе олар қосылмауы мүмкін. Кез келген жағдайда біз қосымша немесе жаңа жиекті қосамыз (A, B), содан кейін оның барлық шыңдары жұп болады. Эйлер графының бар болуының жеткілікті шартының жоғарыда келтірілген конструктивті дәлеліне сәйкес жаңа графиктің кез келген шетінен бастауға болатын Эйлер циклі бар. Эйлер циклін А шыңынан қосылған жиек бойымен (A, B) бастаймыз және оны А шыңында аяқтаймыз. Егер қазір жойсақ

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

Тәуелсіз o Эйлер жолының теоремасына сәйкес графиктерде Эйлер жолы бар ма, жоқ па анықтаңыз? (бір штрихпен қайталамай, бір төбеден басталып, екіншісінде аяқталатын сурет салуға болады ма). Бар болса, оны табыңыз (оны қалай жасау керектігін көрсетіңіз)

Есеп 7. 2. Қиялдағы қалаға арналған Кенигсберг көпірлері туралы (тәуелсіз) o Суретте ойдан шығарылған қаланың жоспары көрсетілген, оны Эйлер өз жұмысында суреттеген. Эйлер жоспарының графигін салыңыз және онда Эйлер циклінің бар-жоғын анықтаңыз? Ал Эйлер жолы? Егер иә болса, оны табыңыз.

Тапсырма 8. Хайуанаттар бағы (өз бетімен) o Суретте хайуанаттар бағының сызбасы көрсетілген (графиктің төбелері – кіреберіс, шығу, қиылыстар, бұрылыстар, тұйық жерлер, ұяшықтар орналасқан жиектер-жол). Гид келушілерге барлық жануарларды көрсетіп, жолдың бір бөлігін бір реттен артық өтпеу арқылы апаратын жолды табыңыз, яғни Эйлер жолын табыңыз.

графикалық теория- бөлім дискретті математика, қасиеттерін зерттеуесептейді . Жалпы мағынада график жиектермен қосылған төбелердің (түйіндердің) жиынтығы ретінде көрсетіледі. Қатаң анықтамада график - бұл жиындар жұбы. G=(V,E), мұндағы V - кез келген есептелетін жиынның ішкі жиыны, ал E - V × V жиынының ішкі жиыны.

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

1. Тақ дәрежелі төбелері жоқ графикте графтың кез келген төбесінен басталатын барлық шеттердің (және әрбір жиегі дәл бір рет кесілген) өтуі бар.
2. Екі және тек екі тақ дәрежелі төбелері бар графикте бір тақ дәрежелі төбеден басталып, екіншісінде аяқталатын айналма жол бар.
3. Екіден көп тақ дәрежелі төбелері бар графикте мұндай өту болмайды.

Графиктер бойынша саяхаттауға қатысты есептердің тағы бір түрі бар. Біз барлық шыңдардан өтетін жолды табуды талап ететін және әрқайсысы арқылы бір реттен көп емес есептер туралы айтып отырмыз. Әрбір төбеден бір-ақ рет өтетін цикл Гамильтон сызығы деп аталады (өткен ғасырдағы әйгілі ирланд математигі, мұндай сызықтарды алғаш зерттеген Уильям Роуэн Гамильтонның құрметіне). Өкінішке орай, берілген графиктің Гамильтондық екенін анықтауға болатын жалпы критерий әлі табылған жоқ, егер солай болса, онда барлық Гамильтон сызықтарын табыңыз.
19 ғасырдың ортасында құрастырылған. төрт түстің мәселесі де қызықты мәселе болып көрінеді, дегенмен оны шешу әрекеттері теориялық және қолданбалы маңызы бар кейбір графикалық зерттеулердің пайда болуына әкелді. Төрт түсті есеп келесідей тұжырымдалған: «Кез келген жазық картаның аумағын төрт түспен бояуға болады, сонда кез келген екі көршілес аумақ әртүрлі түстерге боялады?». Жауап иә деген гипотеза 19 ғасырдың ортасында тұжырымдалған. 1890 жылы әлсіз бекіту дәлелденді, атап айтқанда, кез келген тегіс картаны бес түспен бояуға болады. Кез келген сәйкес келеді тегіс картаоның жалпақ грaf, есептің графиктер бойынша эквивалентті тұжырымын алыңыз: Кез келген жазық графиктің хроматикалық саны төрттен кем немесе оған тең екені рас па? Мәселені шешудің көптеген әрекеттері графтар теориясының бірқатар салаларының дамуына әсер етті. 1976 жылы компьютерді қолдану арқылы мәселенің оң шешімі жарияланды.

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

Графтар теориясындағы алғашқы есептер математикалық рекреациялық есептер мен басқатырғыштарды шешуге қатысты болды. Міне, Эйлердің 1736 жылғы 13 наурыздағы хатынан үзіндіні қайталау: «Маған Кенигсберг қаласында орналасқан және 7 көпір лақтырылған өзенмен қоршалған арал туралы мәселе ұсынылды. Мәселе, кез келген адам оларды үздіксіз айналып, әр көпірден бір-ақ рет өте алады ма. Содан кейін маған мұны әлі ешкім жасай алмағанын хабарлады, бірақ бұл мүмкін емес екенін ешкім дәлелдеген жоқ. Бұл сұрақ маған қарапайым болғанымен, назар аударуға тұрарлық болып көрінді, өйткені оны шешу үшін геометрия да, алгебра да, комбинаторлық өнер де жеткіліксіз. Көп ойланғаннан кейін мен толық сенімді дәлелге негізделген оңай ережені таптым, оның көмегімен барлық есептерде мұндай айналымды кез келген сан және ерікті орналасқан көпірлер арқылы жасауға болатынын немесе болмайтынын бірден анықтауға болады. . Кенигсберг көпірлерін схемалық түрде келесідей бейнелеуге болады:

Эйлер ережесі:

1. Тақ дәрежелі төбелері жоқ графикте графтың кез келген төбесінен басталып, барлық шеттердің (сонымен қатар әрбір жиегі бір рет дәл кесілген) өтуі болады.

2. Екі және тек екі тақ дәрежелі төбелері бар графикте бір тақ дәрежелі төбеден басталып, екіншісінде аяқталатын айналма жол бар.

3. Екіден көп тақ дәрежелі төбелері бар графикте мұндай өту болмайды.

Графиктер бойынша саяхаттауға қатысты есептердің тағы бір түрі бар. Біз барлық шыңдардан өтетін жолды табуды талап ететін және әрқайсысы арқылы бір реттен көп емес есептер туралы айтып отырмыз. Әрбір төбеден бір-ақ рет өтетін цикл Гамильтон сызығы деп аталады (өткен ғасырдағы әйгілі ирланд математигі, мұндай сызықтарды алғаш зерттеген Уильям Роуэн Гамильтонның құрметіне). Өкінішке орай, берілген графиктің Гамильтондық екенін анықтауға болатын жалпы критерий әлі табылған жоқ, егер солай болса, онда барлық Гамильтон сызықтарын табыңыз.

19 ғасырдың ортасында құрастырылған. төрт түстің мәселесі де қызықты мәселе болып көрінеді, дегенмен оны шешу әрекеттері теориялық және қолданбалы маңызы бар кейбір графикалық зерттеулердің пайда болуына әкелді. Төрт түсті есеп келесідей тұжырымдалған: «Кез келген жазық картаның аумағын төрт түспен бояуға болады, сонда кез келген екі көршілес аумақ әртүрлі түстерге боялады?». Жауап иә деген гипотеза 19 ғасырдың ортасында тұжырымдалған. 1890 жылы әлсіз бекіту дәлелденді, атап айтқанда, кез келген тегіс картаны бес түспен бояуға болады. Кез келген жазық картаны оның қос жазық графигімен салыстыра отырып, есептің графиктер бойынша эквивалентті тұжырымын аламыз: Кез келген жазық графиктің хроматикалық саны төрттен кіші немесе оған тең екені рас па? Мәселені шешудің көптеген әрекеттері графтар теориясының бірқатар салаларының дамуына әсер етті. 1976 жылы компьютерді қолдану арқылы мәселенің оң шешімі жарияланды.

Ерекше ұзақ уақыт бойы шешімін таппаған және басқатырғыштарды қызықтырған тағы бір ескі топологиялық мәселе «электр, газ және сумен қамтамасыз ету мәселесі» ретінде белгілі. 1917 жылы Генри Э. Дудени оған осы тұжырымды берді. Суретте көрсетілген үш үйдің әрқайсысында газ, электр және суды жүргізу қажет.

График теориясы. бір

Графтар теориясының пайда болу тарихы. бір

Эйлер ережесі. бір

Әдебиет

1. Белов графикалық теориясы, Мәскеу, «Наука», 1968.

2. Жаңа педагогикалық және ақпараттық технологияларЕ.С.Полат , Мәскеу, «Академия» 1999

3. Кузнецов О.П., Адельсон-Вельский Г.М. Инженерге арналған дискретті математика. - Мәскеу: Энергоатомиздат, 1988.

4. Кук Д., Байзе Г. Компьютерлік математика. - М.: Наука, 1990.

5. Нефедов В.Н., Осипова В.А. Дискретті математика курсы. - М.: МАИ баспасы, 1992.

6. Кенді О. Графикалық теория. - М.: Наука, 1980.

7. Исмагилов Р.С., Калинкин А.В. Курс бойынша практикалық сабақтарға арналған материалдар: Дискретті математика

ҚАЛАЛЫҚ АВТОНОМИЯЛЫҚ ЖАЛПЫ БІЛІМ БЕРУ МЕКЕМЕСІ № 2 ОРТА БІЛІМ БЕРУ МЕКТЕБІ

Дайындалды

Легкоконец Владислав, 10А сынып оқушысы

Практикалық қолдануГрафикалық теориялар

Жетекші

Л.И. Носкова, математика пәнінің мұғалімі

ст.Брюховецкая

2011

1.Кіріспе……………………………………………………………………………………….3

2. Графикалық теорияның пайда болу тарихы .............................................................................................................................................................................................................................................................................

3. Графтар теориясының негізгі анықтамалары мен теоремалары………………………………………………6

4. Графиктердің көмегімен шешілетін тапсырмалар………………………………………………………..8

4.1 Танымал тапсырмалар……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………8

4.2 Кейбір қызықты тапсырмалар………………………………………………..9

5. Адамдардың әр түрлі салаларындағы графиктерді қолдану .......................................................................................................................................................................................

6. Мәселені шешу .............................................................................................

7. Қорытынды……………………………………………………………………………….13

8. Әдебиеттер тізімі……………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………… …………………………………………………………………………………………………………….

9.Қосымша………………………………………………………………………………15

Кіріспе

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

Көптеген өмірлік мәселелерді шешу ұзақ есептеулерді қажет етеді, кейде бұл есептеулер табыс әкелмейді. Ол осыдан тұрады зерттеу мәселесі. Сұрақ туындайды: оларды шешудің қарапайым, ұтымды, қысқа және талғампаз шешімін табу мүмкін бе? Графиктерді пайдалансаңыз, есептерді шешу оңай ма? Ол анықтады менің зерттеу тақырыбым: «Графтар теориясының практикалық қолданылуы»

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

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

Зерттеу мақсаттары:

1. Осы мәселе бойынша әдебиеттер мен интернет ресурстарын зерттеу.

2. График әдісінің практикалық есептерді шешудегі тиімділігін тексеру.

3. Қорытынды жасаңыз.

Зерттеудің практикалық маңызынәтиже көптеген адамдардың қызығушылығын тудыратыны сөзсіз. Сіздердің араларыңызда отбасыңыздың шежіресін құруға тырысқан жоқсыз ба? Және оны қалай дұрыс жасауға болады? Тасымалдаушы компания басшысы жүкті межелі жерден бірнеше елді мекенге тасымалдау кезінде көлікті тиімді пайдалану мәселесін шешуі керек шығар. Әрбір студент логикалық қан құю тапсырмаларын алды. Олар графиктердің көмегімен оңай шешіледі.

Жұмыста келесі әдістер қолданылады: бақылау, іздеу, таңдау, талдау.

Графтар теориясының пайда болу тарихы

Математик Леонхард Эйлер (1707-1783) графиктер теориясының негізін салушы болып саналады. Бұл теорияның пайда болу тарихын ұлы ғалымның хат-хабарлары арқылы білуге ​​болады. Мұнда Эйлердің 1736 жылы 13 наурызда Санкт-Петербургтен итальяндық математик және инженер Маринониге жазған хатынан алынған латын тіліндегі мәтіннің аудармасы берілген.

«Бірде маған Кенигсберг қаласында орналасқан және жеті көпір лақтырылған өзенмен қоршалған арал туралы мәселе берілді.

[Қосымша 1-сурет]Мәселе, кез келген адам оларды үздіксіз айналып, әр көпірден бір-ақ рет өте алады ма. Содан кейін маған мұны әлі ешкім жасай алмағанын хабарлады, бірақ бұл мүмкін емес екенін ешкім дәлелдеген жоқ. Бұл сұрақ маған қарапайым болғанымен, назар аударуға тұрарлық болып көрінді, өйткені оны шешу үшін геометрия да, алгебра да, комбинаторлық өнер де жеткіліксіз. Көп ойланғаннан кейін мен өте сенімді дәлелге негізделген қарапайым ережені таптым, ол арқылы мұндай есептердің барлығында кез келген сан және ерікті орналасқан көпірлер арқылы мұндай айналымды жасауға болатынын немесе мүмкін еместігін бірден анықтауға болады. Конигсберг көпірлері оларды келесі суретте көрсетуге болатындай етіп орналастырылған [Қосымша 2-сурет], мұндағы А аралды білдіреді, ал В, С және D континенттің бір-бірінен өзен тармақтарымен бөлінген бөліктері

Осы тектес есептерді шешудің әдісі туралы Эйлер былай деп жазды:

«Бұл шешімнің табиғаты бойынша математикаға қатысы жоқ сияқты және маған неге бұл шешімді кез келген адамнан емес, математиктен күту керек екені түсініксіз, өйткені бұл шешім тек ақылмен ғана қолдау табады және Бұл шешімді табу үшін математикаға тән қандай да бір заңдарды тартудың қажеті жоқ.Олай болса, математикаға өте аз қатысы бар сұрақтарды басқаларға қарағанда математиктер шешуі ықтимал екенін қалай анықтайтынын білмеймін ».

Сонда Кенигсберг көпірлерін осы көпірлердің әрқайсысынан бір-ақ рет өту арқылы айналып өтуге болады ма? Жауапты табу үшін Эйлердің Маринониге жазған хатын жалғастырайық:

"Мәселе осы жеті көпірдің барлығын айналып өтіп, әрқайсысынан бір-ақ рет өтуге бола ма, жоқ па, соны анықтау керек. Менің ережем бұл сұрақтың келесі шешіміне әкеледі. Ең алдымен, қанша бөлімнен тұратынын қарау керек. сумен бөлінген - көпірден басқа бірінен екіншісіне басқа ешқандай ауысуы жоқ. бұл мысалмұндай төрт бөлім бар - A, B, C, D. Әрі қарай, осы жеке учаскелерге апаратын көпірлер саны жұп немесе тақ екенін ажырату керек. Сонымен, біздің жағдайда А учаскесіне бес көпір, ал қалғандарына үш көпір апарады, яғни жеке учаскелерге апаратын көпірлердің саны тақ және бұл мәселені шешу үшін жеткілікті. Бұл анықталғанда, біз келесі ережені қолданамыз: егер әрбір жеке учаскеге апаратын көпірлердің саны жұп болса, онда қарастырылып отырған айналма жол мүмкін болар еді және сонымен бірге бұл айналма жолды кез келген учаскеден бастауға болады. Алайда, егер бұл сандардың екеуі тақ болса, тек біреуі тақ болуы мүмкін емес болса, онда тіпті сол кезде де көшу белгіленгендей орын алуы мүмкін, бірақ айналма жолдың басы міндетті түрде осы екі бөлімнің бірінен алынуы керек. тақ сан жолдар.көпірлер. Егер, сайып келгенде, көпірлердің тақ саны апаратын екі бөліктен көп болса, онда мұндай қозғалыс әдетте мүмкін емес ... егер басқасын келтіру мүмкін болса, көбірек күрделі міндеттер, бұл әдіс одан да пайдалы болуы мүмкін және оны елемеуге болмайды.

Графтар теориясының негізгі анықтамалары мен теоремалары

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

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

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

Алдағы уақытта графтың төбелерін латынның A, B, C, D әріптерімен белгілейміз. Кейде граф тұтастай бір арқылы белгіленеді бас әріп.

Анықтама 2.Графиктің ешбір шетіне жатпайтын төбелері оқшауланған деп аталады.

Анықтама 3.Тек оқшауланған төбелерден тұратын график нөл деп аталады - санау .

Белгі: O " – төбелері бар және шеттері жоқ график

Анықтама 4.Әрбір төбелер жұбы жиекпен қосылған график толық деп аталады.

Белгі: U" – n төбелерден және осы төбелердің барлық мүмкін жұптарын қосатын шеттерден тұратын график. Мұндай графикті барлық диагональдары сызылған n-бұрыш ретінде көрсетуге болады

Анықтама 5.Төбенің дәрежесі - бұл төбе жататын жиектер саны.

Анықтама 6.Барлық k төбелерінің градустары бірдей болатын графты k дәрежесінің біртекті графигі деп атайды. .

Анықтама 7.Берілген графиктің толықтауышы деп толық графикті алу үшін бастапқы графикке қосу керек барлық шеттері мен олардың ұштарынан тұратын графикті айтады.

Анықтама 8.Жазықтықта оның шеттері тек төбелерінде қиылысатындай етіп кескіндеуге болатын график жазық деп аталады.

Анықтама 9.Ішінде графтың төбелері мен жиектері жоқ жазық графтың көпбұрышы оның беті деп аталады.

Жазық график және график беттері ұғымдары әртүрлі карталарды «дұрыс» бояуға арналған есептерді шешуде қолданылады.

Анықтама 10.А-дан X-ке дейінгі жол - бұл әрбір екі көршілес жиектің ортақ төбесі болатындай және бірде-бір жиек бір реттен көп кездеспейтіндей А-дан X-ке апаратын жиектер тізбегі.

Анықтама 11.Цикл – бастапқы және соңғы нүктелері бірдей болатын жол.

Анықтама 12.Қарапайым цикл - бұл графтың төбелерінің ешқайсысынан бір реттен артық өтпейтін цикл.

Анықтама 13.ұзақ жол , ілмекке салынған , бұл жолдың жиектерінің саны.

Анықтама 14.Графиктегі екі А және В төбелері, егер онда А-дан В-ге апаратын жол бар болса (болмаса) қосылған (ажыратылған) деп аталады.

Анықтама 15.График оның әрбір екі төбесі қосылса, ол қосылған деп аталады; егер графикте кем дегенде бір жұп ажыратылған шыңдар болса, онда график ажыратылған деп аталады.

Анықтама 16.Ағаш - циклдары жоқ байланысқан график.

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

Анықтама 17.Жалғыз ағаштардан тұратын ажыратылған графикті орман деп атайды.

Анықтама 18.Барлық n төбелері 1-ден n-ге дейін нөмірленген ағаш төбелері қайта нөмірленген ағаш деп аталады.

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

Графиктер арқылы шығарылатын есептер

Танымал сынақтар

Саяхатшы сатушы мәселесі

Көшпелі сатушы мәселесі комбинаторика теориясындағы әйгілі есептердің бірі болып табылады. Ол 1934 жылы қойылды және ең жақсы математиктер бұл туралы тістерін сындырды.

Мәселе туралы мәлімдеме келесідей.
Саяхатшы (саяхатшы көпес) бірінші қаладан шығып, белгісіз ретпен 2,1,3..н қалаларды бір рет аралап, бірінші қалаға оралуы керек. Қалалар арасындағы қашықтық белгілі. Саяхатшы сатушының тұйық жолы (туры) ең қысқа болуы үшін қалаларды қандай ретпен жүру керек?

Саяхатшы сатушы мәселесін шешу әдісі

Ашкөз алгоритм «Ең жақын (сіз әлі кірмеген) қалаға барыңыз».
Бұл алгоритм «ашкөз» деп аталады, өйткені соңғы қадамдарда ашкөздік үшін қымбат төлеуге тура келеді.
Мысалы, суреттегі желіні қарастырайық [қолданба 3-сурет]тар ромбты бейнелейді. Сатушы 1-қаладан бастасын. «Жақын қалаға бару» алгоритмі оны 2-ші қалаға, содан кейін 3-ке, содан кейін 4-ке апарады; соңғы қадамда сіз ромбтың ұзын диагоналы бойымен оралып, ашкөздік үшін төлеуге тура келеді. Нәтиже - ең қысқа емес, ең ұзақ тур.

Кенигсберг көпірлерінің мәселесі.

Тапсырма келесідей тұжырымдалған.
Конигсберг қаласы Прегель өзені мен екі аралдың жағасында орналасқан. Қаланың әртүрлі бөліктерін жеті көпір байланыстырды. Жексенбі күндері қала тұрғындары қаланы аралап шықты. Сұрақ: Әр көпірдің үстінен дәл бір рет өтіп, үйден шығып, қайтып келетіндей серуендеуге бола ма?
Прегель өзеніндегі көпірлер суреттегідей орналасқан[Қосымша 1-сурет].

Көпір схемасына сәйкес графикті қарастырайық [қосымша сурет 2].

Есептің сұрағына жауап беру үшін графтың Эйлер екенін анықтау жеткілікті. (Кем дегенде бір шыңында көпірлердің жұп саны болуы керек). Қаланы аралап жүріп, барлық көпірлерден бір рет өтіп, қайта оралу мүмкін емес.

Бірнеше қызықты сынақтар

1. «Бағдарлар».

1-тапсырма

Естеріңізде болса, аңшы өлі жандарЧичиков атақты помещиктерге бір рет барды. Оларға келесі ретпен барды: Манилов, Коробочка, Ноздрев, Собакевич, Плюшкин, Тентетников, генерал Бетрищев, Петух, Констанжолго, полковник Кошкарев. Чичиков сызған диаграмма табылды өзара реттеуучаскелер мен оларды байланыстыратын ауылдық жолдар. Чичиков жолдардың бірде-біреуінен бірнеше рет өтпесе, қандай мүлік кімдікі екенін анықтаңыз. [қосымша 4-сурет].

Шешім:

Жол картасы бойынша Чичиков сапарын Е ителгіден бастап, О ителгімен аяқтағанын байқауға болады.Байқаймыз, В және С учаскелеріне екі жол ғана апарады, сондықтан Чичиков осы жолдармен жүруге мәжбүр болды. Оларды жуан сызықтармен белгілейік. Маршруттың А арқылы өтетін учаскелері анықталады: АС және АВ. Чичиков АЕ, АК және АМ жолдарында жүрмеген. Оларды сызып тастайық. Қалың сызықпен белгілейік ED ; DK сызып тастаңыз. MO және MN сызып тастаңыз; қалың сызықпен белгілеңіз MF ; сызып тастаңыз FO ; біз қалың сызықпен FH , NK және KO белгілейміз. Берілген шарт бойынша мүмкін болатын жалғыз жолды табайық. Ал біз мынаны аламыз: Е мүлкі - Маниловқа, Д - Коробочкаға, С - Ноздревке, А - Собакевичке, В - Плюшкинге, М - Тентетниковке, Ф - Бетрищевке, Н - Петухқа, К - Констанжолго, О - Кошкаревке. [5-сурет].

2-тапсырма

Суретте ауданның картасы көрсетілген [қосымша сурет 6].

Сіз тек көрсеткілердің бағытымен қозғала аласыз. Әрбір нүктеге бір реттен көп емес баруға болады. 1-тармақтан 9-тармаққа қанша жолмен жетуге болады? Қай бағыт ең қысқа, қайсысы ең ұзын.

Шешім:

Схеманы 1-төбеден бастап ағашқа ретімен «стратификациялаңыз». [қолданба 7-сурет]. Ағаш алайық. 1-ден 9-ға дейін алудың мүмкін жолдарының саны ағаштың «ілулі» шыңдарының санына тең (олардың 14-і бар). Әлбетте, ең қысқа жол 1-5-9; ең ұзыны 1-2-3-6-5-7-8-9.

2 «Топтар, танысу»

1-тапсырма

Музыкалық фестивальдің қатысушылары кездесіп, мекенжайлары бар конверттермен алмасты. Дәлелдеңіз:

а) конверттердің жұп саны барлығы жіберілді;

б) конверттерді тақ рет ауыстырған қатысушылардың саны жұп.

Шешуі: Фестиваль қатысушылары А 1 , А 2 , А 3 болсын. . . , Ал n - графиктің шыңдары, ал жиектер конверттерді алмастырған жігіттерді бейнелейтін жұп төбелерді қосады. [Қосымша 8-сурет]

Шешім:

а) әрбір A i шыңының дәрежесі А i қатысушысының достарына берген конверттерінің санын көрсетеді. Жіберілген конверттердің жалпы саны N N графигінің барлық шыңдарының дәрежелерінің қосындысына тең N = қадам. 1+ қадам. A 2 + +. . . + қадам. Және n -1 + қадам. Ал n , N =2p , мұндағы p - графиктің жиектерінің саны, яғни. N жұп. Сондықтан конверттердің жұп саны жіберілді;

б) N = қадам теңдігінде. 1+ қадам. A 2 + +. . . + қадам. Және n -1 + қадам. Ал n тақ мүшелерінің қосындысы жұп болуы керек және бұл тақ мүшелердің саны жұп болған жағдайда ғана болуы мүмкін. Және бұл конверттерді тақ рет ауыстырған қатысушылардың саны жұп екенін білдіреді.

2-тапсырма

Бірде Андрей, Борис, Володя, Даша және Галя кешке кинотеатрға баруға келісті. Олар кинотеатр мен сеансты таңдау туралы телефон арқылы келісу туралы шешім қабылдады. Сондай-ақ, егер біреуге телефон соғу мүмкін болмаса, онда кинотеатрға сапар тоқтатылады деп шешілді. Кешке барлығы кинотеатрға жиналмады, сондықтан кинотеатрға бару сәтсіз аяқталды. Келесі күні олар кімнің кімге қоңырау шалғанын анықтай бастады. Андрей Борис пен Володяға, Володя Борис пен Дашаға, Борис Андрей мен Дашаға, Даша Андрей мен Володяға, Галя Андрейге, Володяға және Бориске телефон шалған екен. Кім телефон соға алмады, сондықтан кездесуге келмеді?

Шешім:

Бес нүктені сызып, оларды A, B, C, D, E әріптерімен белгілейік. Бұл атаулардың бірінші әріптері. Бір-бірін шақырған жігіттердің есімдеріне сәйкес нүктелерді байланыстырайық.

[қолданба 9-сурет]

Суреттен жігіттердің әрқайсысы - Андрей, Борис және Володя - барлығына телефон соққанын көруге болады. Сол себепті бұл жігіттер кинотеатрға келді. Бірақ Галя мен Даша бір-біріне қоңырау шала алмады (D және D нүктелері сегментпен қосылмаған), сондықтан келісімге сәйкес олар кинотеатрға келмеді.

Графиктерді адамдар өмірінің әртүрлі салаларында қолдану

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

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

Молекулалық графиктер, стереохимияда және құрылымдық топологияда, кластерлер химиясында, полимерлерде және т.б. қолданылады, молекулалардың құрылымын көрсететін бағытталмаған графиктер. [қолданба 10-сурет]. Бұл графиктердің төбелері мен шеттері сәйкес атомдарға және олардың арасындағы химиялық байланыстарға сәйкес келеді.

Молекулалық графиктер және ағаштар: [қолданба 10-сурет] a, b - мультиграфтар resp. этилен және формальдегид; ин-моль. пентанның изомерлері (4, 5 ағаштары 2 ағашқа изоморфты).

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

Протеиндік желілер

Ақуыз желілері - организмде болып жатқан өзара байланысты процестерді бақылайтын, жасушада бірігіп және үйлестірілген түрде қызмет ететін физикалық өзара әрекеттесетін белоктар топтары [қолданба сур. он бір].

Иерархиялық жүйе графигіағаш деп аталады. Ағаштың айрықша ерекшелігі оның кез келген екі шыңының арасында бір ғана жолдың болуы. Ағашта циклдар мен циклдар жоқ.

Әдетте, иерархиялық жүйені білдіретін ағаштың бір негізгі шыңы болады, ол ағаштың түбірі деп аталады. Ағаштың әрбір шыңында (түбірден басқа) бір ғана ата-баба бар - ол белгілеген нысан бір жоғарғы деңгейлі сыныпқа жатады. Ағаштың кез келген шыңы бірнеше ұрпақты тудыруы мүмкін - төменгі деңгейдегі кластарға сәйкес шыңдар.

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

Менің отбасылық ағашымның мысалы [қосымша сурет 12].

Тағы бір мысал. Суретте библиялық отбасы ағашы көрсетілген [қосымша сурет 13].

Мәселені шешу

1. Тасымалдау тапсырмасы. Краснодар қаласында Крымск, Темрюк, Славянск-на-Кубань және Тимашевск қалаларында мүмкіндігінше аз уақыт пен жанар-жағармай жұмсап, кері қайтару үшін бір айналымда отырғызу керек шикізат базасы болсын. Краснодарға.

Шешім:

Алдымен барлық мүмкін болатын маршруттардың графигін құрайық. [қолданба 14-сурет], осы елді мекендер арасындағы нақты жолдар мен олардың арасындағы қашықтықты ескере отырып. Бұл мәселені шешу үшін бізге басқа график, ағаш құру керек [қолданба сурет 15].

Шешімнің ыңғайлылығы үшін қалаларды сандармен белгілейміз: Краснодар - 1, Крымск - 2, Темрюк - 3, Славянск - 4, Тимашевск - 5.

Бұл 24 шешімге әкелді, бірақ бізге ең қысқа жолдар ғана қажет. Барлық шешімдердің екеуі ғана қанағаттандырылды, бұл 350 км.

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

Трансфузияға арналған логикалық тапсырма.Бір шелекте 8 литр су бар, ал 5 және 3 литрлік екі қазан бар. бес литрлік кастрюльге 4 литр су құйып, шелекке 4 литр қалдыру керек, яғни суды шелек пен үлкен кастрюльге бірдей құйыңыз.

Шешім:

Кез келген сәттегі жағдайды үш санмен сипаттауға болады [қосымша 16-сурет].

Нәтижесінде біз екі шешімді аламыз: біреуі 7 қозғалыста, екіншісі 8 қозғалыста.

Қорытынды

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

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

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

Көлік мәселесін немесе отбасылық ағашты құрастыру мәселесін шешкенде, мен графикалық әдіс, әрине, қызықты, әдемі және көрнекі деген қорытындыға келдім.

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

Бұл ғылыми жұмыста математикалық графиктер, олардың қолданылу салалары қарастырылып, графиктер көмегімен бірнеше есептер шығарылады. Графтар теориясының негіздерін білу өндірісті басқарумен, бизнеспен байланысты әртүрлі салаларда қажет (мысалы, құрылыс желісінің диаграммасы, поштаны жеткізу кестелері). Сонымен қатар, ғылыми жұмысты орындау барысында WORD мәтіндік редакторында компьютерде жұмыс істеуді меңгердім. Осылайша, тапсырмалар ғылыми жұмысаяқталды.

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

Әдебиет

Берге К.Графикалық теория және оның қолданылуы. -М.: ИИЛ, 1962 ж.

Кемени Дж., Снелл Дж., Томпсон Дж.Ақырлы математикаға кіріспе. -М.: ИИЛ, 1963 ж.

Кен О.Графиктер және олардың қолданылуы. -М.: Мир, 1965 ж.

Харри Ф.График теориясы. -М.: Мир, 1973 ж.

Зыков А.А.Ақырлы графиктер теориясы. -Новосибирск: Наука, 1969 ж.

Березина Л.Ю.Графиктер және олардың қолданылуы. -М.: Білім, 1979. -144 б.

«Сорос білім беру журналы» № 11 1996 («Тегіс графиктер» мақаласы);

Гарднер М. «Математикалық бос уақыт», М. «Мир», 1972 (35-тарау);

Олехник С.Н., Нестеренко Ю.В., Потапов М.К. «Ескі ойын-сауық мәселелері», М.«Наука», 1988 (2 бөлім, 8-бөлім; 4-қосымша);

Қолдану

Қолдану

П

Күріш. 6

Күріш. 7

Күріш. сегіз

қолдану

Қолдану

Қолдану

Қолдану

П

Күріш. он төрт

қолдану

Қолдану

2016 оқу жылы Жыл

1. Кіріспе

2. Графтар теориясының пайда болу тарихы

3. Графтар теориясының негізгі түсініктері

4. Графтар теориясының негізгі теоремалары

5. Графиктерді компьютерде бейнелеу тәсілдері

6. Графтар теориясындағы есептерге шолу

7. Қорытынды

8. Әдебиеттер

Кіріспе

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

Графтар теориясының пайда болу тарихы.

1. Кенигсберг көпірлерінің мәселесі.Суретте. 1-суретте Кенигсберг (қазіргі Калининград) қаласының орталық бөлігінің схемалық жоспары көрсетілген, оның ішінде Пергол өзенінің екі жағалауы, ондағы екі арал және жеті байланыстырушы көпір бар. Тапсырма – жердің төрт бөлігін түгел айналып, әр көпірден бір рет өтіп, бастапқы нүктеге оралу. Бұл мәселені Эйлер 1736 жылы шешкен (шешім жоқ екені көрсетілген).

күріш. бір

2. Үш үй мен үш құдық мәселесі.Үш үй мен үш құдық бар, әйтеуір ұшақта орналасқан. Әр үйден әр құдыққа жолдар қиылыспайтындай етіп сызыңыз (2-сурет). Бұл мәселені 1930 жылы Куратовский шешкен (шешім жоқ екені көрсетілген).

күріш. 2

3. Төрт түс мәселесі.Жазықтықтағы қиылыспайтын аймақтарға бөлу карта деп аталады. Картадағы аймақтар бар болса, көршілер деп аталады ортақ шекара. Тапсырма картаны екі көршілес аумақ бірдей түспен толтырылмайтындай етіп бояу (3-сурет). Өткен ғасырдың соңынан бастап бұл үшін төрт түстің жеткілікті екендігі туралы гипотеза белгілі болды. 1976 жылы Appel және Heiken төрт түсті мәселенің шешімін жариялады, ол компьютерді пайдаланып опцияларды санауға негізделген. Бұл мәселені «бағдарлама бойынша» шешу қызу пікірталас тудырған прецедент болды. Жарияланған шешімнің мәні төрт түсті теоремаға потенциалды қарсы мысалдардың үлкен, бірақ шектеулі санын (шамамен 2000) санап шығу және ешбір жағдайдың қарсы мысал емес екенін көрсету. Бұл санауды бағдарлама шамамен мың сағат суперкомпьютер жұмысында орындады. Алынған шешімді «қолмен» тексеру мүмкін емес - санау мөлшері адам мүмкіндіктерінен әлдеқайда асып түседі. Көптеген математиктер сұрақ қояды: мұндай «бағдарламалық дәлелдемені» жарамды дәлел деп санауға бола ма? Ақыр соңында, бағдарламада қателер болуы мүмкін ... Бағдарламалардың дұрыстығын ресми дәлелдеу әдістері талқыланатын сияқты күрделі бағдарламаларға қолданылмайды. Тестілеу қателердің жоқтығына кепілдік бере алмайды және бұл жағдайда мүлде мүмкін емес. Осылайша, авторлардың бағдарламашы біліктілігіне сүйену және олар бәрін дұрыс жасады деп сену қалады.

Күріш. 3

Графтар теориясының негізгі түсініктері

1) G(V,E) графигіекі жиынның жиыны – бос емес V жиыны (төбелер жиыны) және V жиынының екі элементті ішкі жиындарының E жиыны (E – жиектер жиыны).

2) бағдарланған(х, у) түріндегі реттелген жұп төбелерінің жиыны болатын граф деп аталады, мұнда х басы, ал у доғаның соңы деп аталады. Доға (x, y) жиі ретінде жазылады. Сондай-ақ доғаның х шыңынан у шыңына, ал у шыңына апаратыны айтылады. іргелесжоғарғы x.

3) Е жиынының элементі жұп бола алатын болса бірдей(әртүрлі емес) V элементтері болса, онда Е жиынының мұндай элементі деп аталады цикл, және график деп аталады циклдері бар график(немесе псевдограф).

4) Егер E жиыны болмаса, бірақ орнатуқұрамында бірнеше бірдей элементтер болса, онда бұл элементтер деп аталады бірнеше жиектер, және график деп аталады мультиграф.

5) Е жиынының элементтері міндетті түрде екі элемент емес, V жиынының кез келген ішкі жиындары болса, онда Е жиынының мұндай элементтері деп аталады. гипердоғалар, және график деп аталады гиперграф.

6) Функция орнатылған болса F:V→Mжәне/немесе F: E → M, содан кейін жиынтық Мжиынтық деп аталады ескертпелер, және график деп аталады тегтелген(немесе жүктелді). Жазбалар жиынтығы ретінде әдетте әріптер немесе бүтін сандар пайдаланылады. Егер функция Финъекциялық болып табылады, яғни әртүрлі төбелердің (жиектердің) әртүрлі белгілері бар, содан кейін график деп аталады. нөмірленген.

7) Субграф G′(V′,E′) графигі деп аталады, мұндағы және/немесе .

а) V′ = V болса, онда G′ деп аталады негізгі G тармақшасы.

б) Егер болса, онда G графигі шақырылады меншікГ графының тармақшасы.

в) G′(V′,E′) тармақшасы G(V,E)-тің тиісті графигі деп аталады, егер G′ G-тің барлық мүмкін болатын шеттерін қамтыса.

8) Дәреже (валенттілік)шыңдар - осы төбеге түсетін жиектер саны (оған іргелес шыңдар саны).

9) Маршрутграфикте кез келген екі көршілес элемент түсетін төбелер мен шеттердің ауыспалы тізбегі деп аталады.

а) Егер , онда маршрут жабық, әйтпесе ашық.

б) Егер барлық жиектер анық болса, онда маршрут шақырылады шынжыр.

в) Егер барлық шыңдар (демек, шеттер) бөлек болса, онда маршрут шақырылады қарапайым тізбек.

г) Тұйық тізбек деп аталады цикл.

д) Тұйық қарапайым тізбек деп аталады қарапайым цикл.

f) Циклдері жоқ график деп аталады ациклді.

ж) Диграфтар үшін тізбек деп аталады арқылы, және цикл болады контур.

күріш. 4. Маршруттар, тізбектер, циклдар

Мысал

Диаграммасы 4-суретте көрсетілген графикте:

1. v 1 , v 3 , v 1 , v 4 - маршрут, бірақ тізбек емес;

2. v 1 , v 3 , v 5 , v 2 , v 3 , v 4 - тізбек, бірақ жай тізбек емес;

3. v 1 , v 4 , v 3 , v 2 , v 5 - қарапайым тізбек;

4. v 1 , v 3 , v 5 , v 2 , v 3 , v 4 , v 1 - цикл, бірақ қарапайым цикл емес;

5. v 1 , v 3 , v 4 , v 1 - қарапайым цикл.

10) Егер графикте графтың барлық шеттерін бір рет қамтитын цикл (міндетті түрде қарапайым емес) болса, онда мұндай цикл деп аталады Эйлерцикл.

11) Егер графикте графтың барлық төбелері бар қарапайым цикл болса (бір рет), онда мұндай цикл деп аталады Гамильтондықцикл.

12) ағашциклсыз байланысқан график деп аталады.

13) Остовомграфтың барлық төбелерін қамтитын ағаш деп аталады.

14) СәйкестікЕкеуі қатарласпайтын жиектер жиынтығы.

15) Сәйкестік деп аталады максимумегер оның жоғарғы жиыны тәуелсіз болмаса.

16) Графиктің екі төбесі қосылғанегер оларды байланыстыратын қарапайым тізбек болса.

17) Барлық төбелері қосылған график деп аталады қосылған.

18) Тек оқшауланған төбелерден тұратын график деп аталады әбден үйлесімсіз.

19) Маршрут ұзындығыондағы жиектер санын (қайталаулармен) деп атайды.

20) Қашықтық u және v төбелерінің арасындағы ең қысқа тізбектің ұзындығы, ал ең қысқа тізбектің өзі деп аталады. геодезиялық.

21) диаметрі G графигі – ең ұзын геодезиялық ұзындығы.

22) эксцентристік G(V,E) қосылған графтағы v төбесінің V төбесінен G графигінің басқа төбелеріне дейінгі ең үлкен қашықтығы.

23) Радиус G графигі төбелердің эксцентриситеттерінің ең кішісі деп аталады.

24) v Vertex деп аталады орталық, егер оның эксцентриситеті графиктің радиусымен сәйкес келсе.

25) Орталық төбелер жиыны деп аталады орталықграфик.

күріш. 5 Графиктердің төбелері мен центрлерінің эксцентриситеттері (ерекшеленген).

Ұқсас ақпарат.