Графтар

Мазмұны

1.Кіріспе...................................................................................................5

2.Графтарға байланысты негізгі терминдер мен қажетті фактілер. ..7

3.Платондық графтар. ............................................................................20

  1.Тетраэдр..............................................................................................20

  2.Гексаэдр. .............................................................................................21

  3.Октаэдр................................................................................................21

  4.Додекаэдр. ..........................................................................................21

  5.Икосаэдр. ............................................................................................22

4.Архимед денелерінің графтары. .........................................................23

  1.Қиық тетраэдр. ...................................................................................23

  2.Қиық октаэдр. .....................................................................................23

  3.Қиық гексаэдр. ....................................................................................25

  4.Қиық додекаэдр. .................................................................................25

  5.Қиық икосаэдр. ...................................................................................26

  6.Кубооктаэдр. .......................................................................................26

  7.Қиық кубооктаэдр. .............................................................................27

  8.Икосододекаэдр. .................................................................................28

  9.Қиық икосододекаэдр. .......................................................................28

  10.Ромбокубооктаэдр. ...........................................................................28

  11.Ромбоикосододекаэдр. .....................................................................28

  12.Қисық куб. .........................................................................................28

  13.Қисық додекаэдр. ..............................................................................28

5.Басқа жасанды  денелер. .......................................................................29

  1.Призмалар. ...........................................................................................29

  2.Антипризмалар. ...................................................................................29

  3.Алтыжақты куб. ...................................................................................30

  4.Ромбылық додекаэдр,. .........................................................................30

  5.Жүздіктер. .............................................................................................30

6.Қорытынды..............................................................................................32

7.Пайдаланылған әдебиеттер тізімі..........................................................33

                                                      Аннотация

Ғылыми жобаның мақсаты: Платондық және архимедтік графтардың, оларға ұқсас денелердің маңызды қасиеттерін, басқа да ұсыныстарды зерттеу.

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

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

  Тақырыптың жаңашылдығы: Лакольді және қарапайым жолдардың  көмегімен жартылай дұрыс полиэдрлардың  құрылымы есептеледі, дұрыс полиэдрлардың  ұтымды жазылу алгоритмі берілді. Күрделі денелердің жайылымын бірнеше түрде беруге болады.Платондық және Архимедтік денелердің жайылымдарында симметриалық қатаң сақталатындықтан математикада әртүрлі әмбебап денелерді, оларды ұтымды орналастыруды қарастыру кезінде графтарды қолдану жұмысты  жеңілдетеді.

Зерттеу кезеңдері: Зерттеу  жұмысында қажетті теоремалар мен түсініктері беріледі, осы теоремалары қолданылып Платон денелерінің жайылымдары   құрылады. Әрбір дененің өзіне тән қасиетін  қарастыра келе Эйлерлік мінездемесі табылып, қарпайым дененелерден күрделі денелерді алудың оңай тәсілдері көрсетілді.

Жұмыстың нәтижесі: Осы күрделі денелердің жайылымын бірнеше түрде беруге болатыны тұжырымдалып, жайылымы  жасалды.Локальді және қарапайым жолдардың  көмегімен жартылай дұрыс полиэдрлардың  құрылымы есептеледі, дұрыс полиэдрлардың  ұтымды жазылу алгоритмі берілді.

                                                      Аннотация

Целью научного проекта является исследование важнейших своиств графов платоновых и архимедовых и близких к ним тел .

Гипотеза:Так как в укладках  Архимедовых и Платоновых тел сохраняется строго симметричность,их использование позволит облегчить задачи в математике и информатике,связанные с разными телами и их строениями.

Актуальность темы: Графовые свойства архимедовых тел и их производных мало изучены поэтому представляют определенный интерес вопросы эффективного построения их укладок, наличия в них эйлеровых и гамильтоновых обходов с подсчетом их количества.Использование графов существенно облегчает исследование более трудных (не элементарных) задач, как построение и изучение групп движений этих тел, рассмотрение различных алгоритмов генерации перестановок – “универсальных объектов“ (кирпичиков) как в математике (симметрические группы), так и в информатике(задачи сортировки и поиска информации).

Новизна темы: Лаконично и просто с помощью элементарных средств вычисляется основание характеристики полуправильных полиэдров, дается эффективный алгоритм построения укладок из исходных правильных полиэдров.

Этапы исследования:В исследовательной работе представлены необходимые теоремы и термины, сделаны укладки тетраэдра, гексаэдра, октаэдра, додекаэдра, икосаэдра, используя эти же теоремы.Имея ввиду собственные своиства каждой фигуры, найдены их эйлерова характеристики, представлены так же, самые удобные пути получения трудных по строению фигур.Делается вывод:Можно представить разные укладки этих трудных по строению фигур.

Abstract

Objective scientific project: a study critical svoistv (planarity, Euler, Hamiltonian) Platonic and Archimedean graphs and close to the bodies of their applications in mathematics and other fields.

A topical issue: graph properties Archimedean bodies and their derivatives poorly understood, so the effective build their ukladok, the availability of Euler and Hamiltonian aside to count their numbers represent a certain interes. Ispolzovanie graphs significantly facilitates the study more difficult (not elementary) tasks, such as building and study groups, movements of the bodies, to consider different algorithms generate permutations - "universal objects (bricks) in mathematics (symmetric group) and Informatics (task sorting and retrieval).

Novelty topics: the basis of semi-polyhedra is computed using the basic tools succinctly and simply, an effective algorithm for constructing ukladok from the right baseline poliedrov.V research the necessary theorems and terms made laying tetrahedron, geksaedra, octahedron, dodecahedron, icosahedron, used the same theorem. We find Euler characteristics of each figure, because imeyas own svoistva each of them represented the most convenient ways to obtain hard figures on the structure of figur.Delaetsya simple conclusion: You can submit a different stacking these difficult in the structure of the figures.

                                                           Кіріспе

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

Зерттеу  жұмысында қажетті теоремалар мен түсініктері беріледі.Осы теоремалары қолданылып Платон денелерінің жайылымдары   құрылады.Әрбір дененің өзіне тән қасиетін  қарастыра келе Эйлерлік мінездемесі табылып, қарпайым дененелерден күрделі денелерді алудың оңай тәсілдері көрсетілді.

Осы күрделі денелердің жайылымын бірнеше түрде беруге болатыны тұжырымдалып, жайылымы  жасалып, сызбада көрсетілді. Локальді және қарапайым жолдардың  көмегімен жартылай дұрыс полиэдрлардың  құрылымы есептеледі, дұрыс полиэдрлардың  ұтымды жазылу алгоритмі берілді.

Көпжақтылар-жазық көпбұрыштардың (полигонның) жиынтығы.

Кез келген полигонның төбесі полиэдр төбесі деп аталады, ал оның жағы полиэдрдің қабырғасы, полигоның өзі-полиэдрдің жағы деп аталады.

Полиэдр-дөңес, егер ол өзінің кез-келген жағының жазықтығының тек бір жағында жатса. Дөңес полиэдрдің ең негізгі ерекшелігі, оның эйлерлік мінездемесінің екіге тең болатындығында: Ɛ(Р)=n-m+g=2, бұл жерде n-төбелер саны, m-қабылғалар саны, g-жақтар саны.

Дұрыс полиэдр-барлық жақтары тең дұрыс полигондар болатын дөңес полиэдр. Оның әр төбесіне бірдей қабырғалар саны сай келеді. Дұрыс  полиэдрдің тек бес түрі бар: Дөңес полиэдрлардан басқа, дөңес емес дұрыс полиэдрлардың Кеплер-Пуансо ашқан төрт түрі бар.

 Платондық денелер және олардың мінездемесі.

1.Графтың негізгі терминдері мен қажетті дәлелдеулер.

G графы деп  Х төбелер жиынынан және олардың кейбіреулерін қосатын сызықтардан тұратын  жиынды айтады. Доға деп бағытталған қабырғаны ұғамыз.Сонымен, G графы екі элементтен тұрады: қабырғадан,төбеден.Оның белгіленуі: G(Х,Е), мұндағы Х-төбелер жиыны,Е-қабырғалар жиыны.

Егер Е жиынында барлық жұптар реттелген (қабырғалары бағытталған) болса,онда бұл-орграф.Граф төбелері қабырғамен қосылмауы (іргелес емес), төбелері қабырғамен қосылуы(іргелес) тіпті көптеген қабырғалармен (еселі) қосылған болуы мүмкін.Сонымен қатар төбенің өзі-өзімен қосылуы мүмкін(жіп түрінде).

 Егер х төбесін басқа бір төбемен қосатын болса,онда х төбесі Еx қабырғасына қарсы жатады.

                        Ішкі граф, толық граф, ноль-граф, қосымша граф.

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

      Егер ішкі графтың төбелері графтың өзінің төбелерімен сәйкес келсе, онда бұл негізгі ішкі граф деп аталады.

V жиынының төбелерінен туындаған ішкі граф деп V жиынынның төбелерінен және тек екі ұшы ішкі графта жататын қабырғалардан құралған ішкі графты атаймыз.

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

а және b төбелері іргелес деп аталады егер аларды өосатын Е қабырғасы

                 a                     E                        b        a.               b.

              а және b төбелері іргелес                        а және b төбелері іргелес емес

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

                                   а

Графтың төбелерінің саны немесе  жиынының қуаты реттелген граф деп аталады. n –ші ретті G графы Gn түрінде белгіленеді.

Кn – n ретті толық граф деп кез келген екі төбесі іргелес болатын n төбелі графты атаймыз.

 болатын толық графтар төменде көрсетілген:

   К1           К2                К3                            К4                                 К5

Кn толық графтың қабырғасына тұратын Vn жиыны n- ретті Gn графтардың жиынының арасындағы қабырғаларының саны максимум болатын жиын, Кn анықтамасы бойынша, оның кез келген екі қабырғасы іргелес болғандықтан оның қуаты Vn=Cn*Cn=n(n-1)/2.Реті n- ге тең  нольграф(бос граф), оның қабырғалары жоқ.Ол n аластатылған төбелерден тұрады,және графтар алгебрасында нольдің ролін атқарады.G(Х,Е) графының толықтауышы деп төбелерінің жиыны Х - тің төбелер жиынымен беттеседін және оның кез келген екі төбесі іргелес болады,сонда ,және тек сонда ,егер олар С1 графында іргелес болмаса ,яғни G1 =G (Х,Е), мұнда Е қабырғалар жиыны  Е - нің V - ға дейінгі толықтауышы. V – Кn толық графының қабырғалар жиыны: Е1 = V / Е.Бұдан G және оның толықтауышының G1-дің қосындысы толық графқа тең.

Графтың төбелерінің дәрежесі, және оның қабырғаларының саны.

G n графының а төбесінің дәрежесі деп,оған инцидентті қабырғалар санын айтамыз.0≤т≤n-1 екені анық.Ноль дәрежелі графтың төбелері оқшауланған, ал бірінші дәрежелі граф аяқтаушы ,ілінген немесе бет (висячей.или листом) деп аталады.

G n графының төбелерінің {t(a1),…,t(an)} дәрежелерінің жиыны – оның маңызды мінездемесі болып табылады және ол арқылы граф қабырғаларының N саны анықталады.

 Теорема 1 .N=N(Gn)=(t(ai)+...+t(an))/2, яғни екі еселенген қабырғалар саны оның төбелерінің қосындысына  тең.

Теореманың тұжырымының дұрыстығы оның дәрежелерінің қосындысында оның әр төбесі екі рет ескеріледі.

  Салдар 1. Шекті графта тақ дәрежелі төбелер саны – жұп.

Егер графтың кез-келген төбесінің дәрежесі r-ге тең болса, онда бұл r граф r-дәрежелі біртекті граф деп аталады.

Салдар 2. r дәрежелі тұрақты Gn,r графының қабырғалар саны N(G)=n*r/2.Себебі  n ретті тұрақты n-1 дәрежелі граф,онда оның қабырғаларының саны  Vn=n(n-1)/2=C2n, мұндағы  Cmn  n элементтен m-нен алынған терулер Cmn=n!/(m!(n-m)!) саны.Үшінші дәрежелі тұрақты граф кубтық граф болады.Бұл теоремадан r-дің тақ болу мүмкіндігі тек n - нің жұп болу жағдайында ғана бар екенін көреміз.

 Теорема2. Кез - келген Gп(п≥2) графында бірдей дәрежелі кем дегенде екі төбе

табылады:t(a)=t(b)

Салдар 3. Егер графта дәрежесі бірдей  тек екі ғана төбе табылса,онда нақты түрде ноль дәрежелелі бір төбе немесе n– 1 дәрежелі бір төбе табылады.           

                            Графтың изоморфтылығы.

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

тың изоморфизмі ұғымында келтірілген.

G1(Х1,Е1) және G2(Х2,Е2) екі графы изоморфты, егер олардың  төбелерінің жиыны  арасында өзара бірмәндік сәйкестік бар болса, яғни бір графтың кез келген сыбайлас  төбелер жұбына  екінші графтың кез келген сыбайлас  төбелер жұбы сәйкес келсе.

Теорема-3 .Изоморфты сәйкестікте сәйкестендірілген төбелердің дәрежелері бірдей.

   G1 және G2 изоморфты, а төбесі   G1-ге тиісті болсын. G2-дегі а1-ді а-мен сәйкестендірейік. а және  b сыбайлас болсын. Онда   G1-дің b төбес оның әртүрлі(Е0, Е1,..., Ек ) қабырғаларының шекті тізбегін  айтады іне G2-нің (a`, b`) қабырғасы сәйкес келеді.

Салдар-4. Изоморфты графтардың төбелерінің дәрежелері тең болады.

Мысалы.Тетраэдр графы К4 изоморфты:

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

 Мысалы:

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

рафтан бір қабырғаны алып тастасақ бұл граф планарлы.)

3- призма                                                                   Граф К3,3

                   Граф жолдары және байланысу ұғымы.

Граф жолдары (маршруты)деп - Еі-1  және Еі       көршілес қабырғалары бір төбеде қиылысатындай, оның әртүрлі(Е0, Е1,..., Ек ) қабырғаларының шекті тізбегін  айтады .Сонымен , егер, (Е0, Е1,..., Ек )- жол болса, онда Е0= (а0,а1) Е1= (а1,а2),.... Еm  =(аm, аm+1)олар жолдың ішкі төбелері деп аталады.Барлық төбелері ішкі болатын жол –тұйықталған жол деп аталады. Барлық қабырғалары қос-қостан алғанда әртүрлі болатын жолды  шынжыр деп атаймыз. Тұйықталған шынжыр – цикл деп аталады. Егер шынжырдың немесе циклдің барлық төбесі бір рет кездесетін болса, онда шынжыр немесе цикл– жай деп аталады.

Мысалы:

G5 -  диагональдарының қиылысу нүктесін қосқандағы ABCD тік төртбұрышы:

b                                                   c

a                                                     d

S=( ab, bc, ce, ed, dc) a төбесімен басталып b төбесімен аяқталатын жол. Бұл жол жай жол емес, себебі c төбесі екі рет кездеседі.

S1=(ab, bе, ec, cd, de,еа)- цикл, бірақ жай емес.

S2=(ab, bе, ec, cd, dа)- жай цикл, S3=(ab, bе, ec, cd) – жай шынжыр.

Байланысқан шынжыр деп – оның кез келген a және b төбелерін қосатынS(а,в) жол табылатын шынжырды айтамыз. Бұл жағдайда a және b төбелері байланысқан деп аталады, себебі қабырғалар арқылы a төбесінен b төбесіне өтуге болады.   а мен байланысқан барлық төбелерден туындаған GаG ішкі графты  а төбесінің Gа байланысуының компонентасы деп атаймыз.

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

Теорема 4. Кез-келген қарапайым   графты қиылыспайтын байланыстардың компонентасына бөліктеуге болады. G=G1+…+Gq (q≥1)

Салдар 5. Егер q=1,онда  G графы толығымен бір байланысу компонентасы  болып табылады,яғни G байланысқан граф.Егер  онда G=G1+ G2     екі компоненттіл байланыспаған граф .

(a,b) қабырғасы G графындағы кқпір деп аталады,егер одан a және b төбелерін алып тастағанда байланыспаған граф шықса,яғни, G/ ішкі графы байланбаған   G/= G/{ a,b }

Көпірдің анықталған белгілерін келтірейік:

1. (a,b) қабырғасы көпір болады сонда,тек сонда егер a,b төбелерін қосатын тек бір ғана жол табылса.
2. (a,b) қабырғасы қабырғасы көпір,егер кез-келген S(c,d) жолы а және b төбелерін қамтитын c және d төбелері табылса.
3. (a,b) қабырғасы қабырғасы көпір,сода,тек сонда егер ол ешбір циклға кірмесе.

Графтардың байланысу критериі.

Төменде байланысудың  екі критериі берілген: бірі  граф қабырғаларының саны N арқылы,екіншісі оның  төбелерінің жиыны арқылы.

Теорема  5.

Граф қабырғаларының  саны N:  N Ø С 2n-1 =((n-1)(n-2))/2  болса, онда бұл граф Gn - байланысқан.

Салдар  6.Байланыспаған Gn= Кn-1     {а n} графтың қабырғаларының максимал саны С 2n-1 –ке тең, ал байланысқан графта -  С 2n  және ол Кnтолық графта орындалады.

Теорема 6.

Егер де кез келкен a және b төбелер жұбы үшін t(a)+ t(b)≥ n орындалса, онда бұл Gn граф - байланысқан.

Салдар 7. Егер кез – келген  Gn графының  төбелерінің дәрежесі n/2 – ден кем болмаса, онда бұл граф байланысқан.Графтың t(a)+ t(b)≥ n шартын қанағаттандыратын кез-келген төбелерінің жұбы үшін байланысқан графтың N қабырғаларының  санын бағалайық.Төбелер саны n/2-ге тең болғандықтан әрбір жұбы үшін t(a)+ t(b)≥0 онда қабырғалар саны N  -ден кем емес ,яғни

Ескерту. сондықтан 1- критериге (теорема 5) қабырғаларының саны квадраттар болатын грфтар класы  жатады.

,,...,

Олардың саны   мұнда және     2-критеиге де қабырғаларының саны квадраттар болатын графтар сай келеді  

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

Теорема 7. Gn байланысқан графының  қабырғаларының минималды саны n-1– ге тең және оған ,мысалы ,n төбелерді қосатын жай циклде жетеді.

Циклсіз байланысқан граф ағаш,ал циклсіз жай граф орман деп аталады.Тn  ағашының  n төбесінде n-1 қабырғасы бар, себебі оған енді кем дегенде бір төбе қоссақ, ол цикл құрайды. Бұдан k ағаштан тұратын Fn орманы n төбесінде N(Fn)=n-k төбесі болады. Егер k=1 болса, онда орман бір ағаштан тұрады. Қабырғалардың саны n-1.

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

Gn  графының a және b төбелерінің арақашықтығы d(a,b) деп сол екі төбені қосатын ең қысқа арақашықтықты айтамыз.

a,b€ Gn үшін d(a,b)≤ n-1 екені түсінікті.

Х төбесінен графтың басқа төбелеріне дейінгі ең ұзын арақашықтықты  – эксцентриситет e(x) деп атаймыз.D(a)- графтың диаметрі деп эксцентриситеттің ең үлкенін айтамыз

R(a)-графтың радиусы деп ең кіші эксцентритетті айтамыз.

Ағаштың e(x)=R(a) болатын төбесі оның түбірі деп аталады.

Теорема 9.Әрбір ағаштың бір ғана түбірі немесе екі сыбайлас түбірі болады.

                          1                                                                         1         2

Салдар 8.Диаметрі жұп болатын теректің тек бір тамыры,ал диаметрі тақ

теректе екі сыбайлас тамыр боады.

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

                         2a                                           b  2  

                           2 d  c 2     C4=(a,b,c,d)

      Графтардың айналымы

Граф-эйлер графтары деп аталады, егер онда оның барлық қабырғалары бір рет қатысатын (қарапайым қабырғалы цикл) цикл бар болса.

Теорема-10.

Граф байланысқан және барлық төбелерінің дәрежесі жұп болған жағдайда ғана эйлер графы болады.

Салдар-9.

Графтың тақ дәрежелі тура екі төбесі  болса ғана бұл байланысқан граф эйлер шынжырын(циклін емес) құрай алады, сонымен қатар оның толықтауышы да эйлер шынжырын құрайды.

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

табылатындығын жоққа шығаратын критери  Эйлер критериі сияқты әлі табылған жоқ. Сондықтан бұл жерде жеткіліктілік критериімен шектелеміз.

Теорема-11

Кез келген графтың a,b төбелері үшін олардың дәрежелерінің қосындысы n-нен кем емес болса, онда граф- гамильтон графы. n: t(а)+ t(b ) ≥. n

Салдар-10. [Dirac,1941]

Егер кез келген а төбесінің  дәрежесі   t(а)  n /2 - ден кем болмаса, онда граф гамильтон графы . t(а) ≥ n /2.

Салдар-11.

Қабырғалар саны n 2/4 - ден кем емес граф- гамильтон графы деп аталады. N(G(n,r))= nr/2≥ n 2/4 осыдан r≥ n /2.

Мысалы:Тақ ретті толық Кn графы- эйлер және гамильтон графы және (n-1)/2 гамильтондық циклдерінің бірігуін білдіреді.Сонда, К5 – бесбұрыштың және бесжұлдыздың қосындысы.

                              K5      =          пентагон               +              пентаграмма

Теорема 12.[Понтрягин Л.С,1927ж] Граф-планарлы, егер К5 және К3,3-ке гомеоморфты ішкі графтары жоқ болса.

Салдар 12. Граф-планарлы, егер онда К5 немесе К3,3-ке изоморфты ішкі графтары жоқ болса.

Теорема 13.[Вагнер,1937 ж] Графты К5 немесе К3,3 ішкі графтарына қарай созуға болатын болса ғана ол планарлы граф деп аталады.

 Пентагон мен пентаграмманың қосындысы болып табылатын Петерсеннің оныншы тізбектегі Gp кубтық графы жоспарланбаған, себебі ол айқын жолмен К5 ішкі графына қарай созылады.

                    Петерсен графы G5                                                             К5

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

Ағаш пен орманның шексіз жағы деген ұғым дербес жағдай түрінде енгізілген.Мұнда жақ ретінде суреттің барлық жазықтығы алынады.

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

   Теорема 14.Кез-келген тұйықталмаған жазық граф үшін келесі теңдік орындалады: n-m+g=2.

Салдар 13.Егер графтың эйлерлік мінездемесі үшін Ɛ(Р)=n-m+g=2 шарты орындалса, онда Gp графы – планарлы емес

Мысал:К5 толық графы үшін n=5,m=10,g≥С35=10 және . Ɛ(К5)= 5- 10+ 10≠2,яғни, К5 - планарлы емес.

Жазық графтың барлық жақтары t – бұрыш болғанда,қабырғалар саны m= t(n–2/( t–2) -ге тең. 

Салдар 14.Барлық жақтары үшбұрыш болатын Gn жазық граф үшін қабырғалар санының максималды саны N=3n-6 ге тең. Қабырғалар саны максимал болатын жазық граф – триангулиарлы деп аталады.Кез-келген триангулярдың 3n-6 қабырғасы бар

Салдар 15.Егер граф қабырғаларының  саны N(Gn)>3n-6 болса, онда Gp графы планарлы емес.Егер кез-келген екі үлесті жиын графының қабырғаларының саны  N(Gn)>3n-6 болса, онда ол планарлы емес. . К3,3-те тек жұп жақтар ғана бола алады.Бұның t=4 болғандағы қабырғалар саны m=4(6-2)(4-2)=8 болу керек, бірақ К3,3 –графының қабырғалар саны 9 – ға тең,осыдан бұл графтың планарлы емес екені дәлелденеді.  

1                                                        

2

Теорема 15.Барлық жазық графтың жайылымы қабырғалары тек түзу сызықты кесінділер бола алады.

2.Платондық денелердің графтары.

Кошидің дәлелдеген дұрыс  дөңес көпжақтарды қарастырайық.Оларды Платон денелері деп те атайды.Олар:тетраэдр, октаэдр, куб(гексаэдр), додекаэдр, икосаэдр. 1.Тетраэдр – төрт жағы да дұрыс үшбұрыш болатын пирамида. Яғни, графтық мінездемесі:n=4,m=6,g=4.Ал эйлерлік мінездемесі Ɛ(Р)=n-m+g=2. Мұздың кристалының формасы-тетраэдр. Тетраэдр формасының кең тараған түрі сүт өнімдерін құюда пайдаланатын атақты «Tetrapack» фирмасының тетрапакеттері болып табылады. Тетраэдр, гексаэдр, октаэдр, додекаэдр, икосаэдр -бес платондық денені құрайды. Платон өзінің «Тимей» шығармасында оттың, ауаның, судың, жердің және эфирдің атомдарына осы бес фигураның формаларын сәйкестендірген. Архимед олардың бұрыштарын қиып тастау арқылы тағы бес жартылай дұрыс көпжақтар алған. Осыдан басқа тағы сегіз архимедттік денелер бар. Олар: кубооктаэдр, ромбокубоэктаэдр қиық кубоэктаэдр, икосододекаэдр, ромбоикосододекаэдр қиық икосододекаэдр, жалпақ танау куб, жалпақ танау додекаэдр.

                    Тетраэдр және оның жайылымы

 Тетраэдрдің жайылуы оның төбеден қараған поекциясы болып табылады.

2.Гексаэдр-(Hexa – 6, hedron-жақ) барлық жағы квадрат болатын үшөлшемді куб.Ол сегізінші ретті кубтық граф. n=8,m=12,g=6.Ал эйлерлік мінездемесі Ɛ(Р)=n-m+g=2. Аспаздық торламаның формасы гексаэдрдің формасына тең.

                              Куб және оның  жайылымы

3.Октаэдр- (Octo-8, hedro-жақ)ол сегізжақ:дұрыс үшбұрыш болатын сегіз жағы бар: n=6,m=12,g=8.Ал эйлерлік мінездемесі Ɛ(Р)=n-m+g=2. Табиғатта оның формасы алтын кристалдарымен бірдей. Октаэдр- төртінші дәрежелі, тұрақты граф.Және тетраэдр мен гексаэдр сияқты кубтық граф.Оның жайылымы төменде көрсетілген

4.Додекаэдр- (Dodeca – 12 деген мағына) онекіжақ.Барлық жағы- дұрыс бесбұрыштар: n=20,m=30,g=12.Ал эйлерлік мінездемесі Ɛ(Р)=n-m+g=2.Бұл да жазық граф.Додекаэдрың гамильтондық циклі алпысқа тең екені есептеулер нәтижесінде дәлелденген.

                  Додекаэдр және оның жайылымы

5.Икосаэдр- жиырмажақ.Барлық жағы- дұрыс үшбұрыштар: n=12, m=30, g=20.Ал эйлерлік мінездемесі Ɛ(Р)=n-m+g=2. Жазылғанда үшбұрышқа айналады.

 Икосаэдр және оның жайылымы

3.Архимедтік денелер графы.

1.Қиық тетраэдр- тетраэдрді төрт төбесінен төрт жазықтықпен қиған кездегі пайда болған фигура. n=12, m=18, g=8.Ал эйлерлік мінездемесі Ɛ(Р)=n-m+g=2.Онда төрт үшбұрышты, төрт алтыбұрышты жақтар бар.Оның екі түрлі жайылымы бар:үшбұрышта және гексагонда.

           Қиық тетраэдр және оның үшбұрыш жақты жайылымы

2. Қиық октаэдр- оның төбелерін сегіз басқа қиюшы жазықтықтармен қиған кезде пайда болатын фигура. n=24, m=36, g=14.Ал эйлерлік мінездемесі Ɛ(Р)=n-m+g=2.Төменде оның шаршы жақты жайылымы берілген:

Қиық октаэдр және оның шаршыдағы жайылымы төбелері алмастырулардан тұратын көпжақ.

Оның төбелерінің саны S4 жиынынан алынған алмастыру 4!=24-ке тең. Sn={f:N→N;N={1,2,…n}}

Sn – n алмастырулар жиыны,ол универсал симметриалы жиын құрайды.Мұнда қиық октаэдрдің кез-келген екі алмастыруларға сәйкестендірілген төбелері іргелес болады,егер бір-біріне тек көршілес транспозиция (i,i+1) арқылы көшірілсе.Мұнда сол жақ (i1,i2) транспозицияны L  арқылы, ортаңғы  (i2,i3) транспозицияны M  арқылы,оң жақ (i3,i4)  транспозицияны  R арқылы белгіледік.Қиық октаэдрдің әр төбесінен транспозициялары L, M, R болатын үш қабырға шығатынын ескерсек  және қиық октаэдрдің квадраттарының

L және R, ал гексагонда  L (R) М-мен кезектеседі.

                                    132              L              312

                             R                                                    R      

                  123                                                                  321    

                             L                                                  L          

                                     213               R             231

                                         L        R

                                          R         L

Қиық октаэдрдің суреті көптеген басылымдарда эмблема түрінде кездеседі.Атап айтқанда,PFA «Дискреттік матеметика» журналының эмблемасы.Мұның мәнісі қиық октаэдр - S4 тобының остов тобы (4- ретті симметриялы топ)-4 элементтен тұратын 24 алмастыру.Мұның өзінде Sn универсам топтың тривиалды емес қасиеті бар.

3.Қиық гексаэдр: n/=24, m/=36, g/=14, Ɛ(Р)=n-m+g=2.Сонымен қатар,кубтың алты шаршы жақтары қиылу кезінде алты сегізбұрышқа(октагон),ал оның сегіз төбесі сегіз үшбұрышқа айналады.Оның жайылымын кубтың жайылымындағы төбелердің орнына үшбұрыштарды қою арқылы алуға болады. 

                            Қиық гексаэдр және оның жайылымы

4.Қиық додекаэдр: n/=60, m/=90, g/=32. Ɛ(Р)=n-m+g=2.Жиырма үшбұрышты жақ,он екі онбұрышты жағы болады.Жазбасы додекаэдрдің жазбасындағы төбелерді үшбұрыштармен алмастырғанда шығатын фигура болып табылады.

                  Қиық додекаэдр және оның жайылымы

5.Қиық икосаэдр.n/=60,m/=90,g/=32.Ɛ(Р)=n-m+g=2.Барлық үшбұрышты жақтар алтыбұрыштарға, ал төбелері бесбұрыштарға айналады.Ол икосаэдр тобының остовы болып табылады.Икосаэдр алгебрадағы бесінші дәрежелі теңдеулерді шешуде маңызды рөл атқарады.Икосаэдр және оның теңдеулерін шешу туралы лекциялар,қиық икосаэдр фирмалық футбол доптарының моделімен түсіндіріледі.

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

Тұжырым 1.Платондық денелер графтары және олардың қималары гамильтондық графтар болып табылады,себебі,бұл графтарда гамильтондық циклдер бар(гамильтондық циклдер- графтың барлық төбелерін қамтитын қарапайым циклдер).Графтардағы гамильтондық циклдедің бар екенін сол графтардың жазбасы арқылы дәлелдеу қиынға соқпайды.

6.Кубооктаэдр.Кубооктаэдр- төбелері куб жақтарының орталары болатын қималар арқылы пайда болады.Оның құрамында алты шаршы,сегіз үшбұрыш бар. n=12,m=24,g=14. Ɛ(Р)=n-m+g=2.Оның ең айқындалған қасиетіне оның төртінші дәрежелі тұрақты граф екендігі жатады.Графтың аты оның куб пен октаэдрге жақындығын көрсетеді:Центрлері бір нүктеде қиылысатын және октаэдрдің диагоналі кубтың жақтарына перпендикуляр болатындай қиылысқан куб пен октаэдр - кубооктаэдрді құрайды.Кубооктаэдрдің құрылысын түсіндірудің ең оңай жолы:Кубтың әр жағына төбелері кубтың қырларының ортасында жататын іштей квадрат саламыз.Кубооктоэдр графы- планарлы және оның екі түрлі жайылымы бар:квадраттаңы және үшбұрыштағы.Кубооктаэдрдің ең негізгі қасиеті:оның екі түрлі жақтары болады:квадрат ,үшбұрыш.Және бір типті жақтың көршілері екінші типті болады.

           Кубооктаэдр және оның жайылымы

Тұжырым 2.Кубооктаэдрдің мінездемесі: n=12,m=24,g=14. Оның ең айқындалған қасиетіне төртінші дәрежелі тұрақты граф екендігі жатады.Ол планарлы,гамильтондық, эйлерлік тұрақты төртінші дәрежелі, 12- ретті  граф.

7.Қиық кубооктаэдр – кубооктаэдрдің  төбелерін жазықтықтармен қиған кезде пайда болатын фигура.

Салдар 1. Планарлы граф –қиық кубооктаэдрдің мінездемесі n=48,m=72,g=26. Ɛ(Р)=n-m+g=2.

Ескерту: Қиық кубооктаэдр – жазбасы квадрат, гексагон, октагон бола алатын жазық кубтық граф.

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

Салдар 2. Қиық икосододекаэдр –жазықтықтары үш типті болатын көпжақ.

9.Қиық икосододекаэдр – жүз жиырмасыншы тізбектегі  планарлы кубтық гамильтондық граф.n=120,m=180,g=62.Ɛ(Р)=n-m+g=2.

10.Ромбокубооктаэдр.Бұл көпжақтың он сегіз жағы квадрат,сегіз жағы үшбұрыш болып табылады.Оны шеткі жақтары квадрат болатын октапризма мен квадраттар мен үшбұрыштардан құралған симметриялы сегізбұрыштының қосылуы арқылы елестетуге болады.

Тұжырым 4. Ромбокубооктаэдр-жиырма төртінші тізбектегі төртінші дәрежедегі планарлы граф.n=24,m=48,g=26.

11.Ромбоикосододекаэдр – n=60,m=120,g=62 болатын алпысыншы тізбектегі төртінші дәрежелі жоспарланған граф.

Тұжырым 5. Ромбоикосододекаэдр – планарлы эйлерлік және гамильтондық граф.

12.Қисық куб – n=24,m=60,g=38 болатын жиырма төртінші тізбектегі бесінші дәрежелі тұрақты планарлы граф болып табылады.

13.Қисық додекаэдр - n=60,m=150,g=92 болатын алпысыншы тізбектегі бесінші дәрежелі жоспарлы гамильтонды граф.

4.Басқа жасанды денелер.

1.Призмалар – негізі дұрыс  К көпбұрыштылар болып келетін цилиндрлер. Cонымен, куб - бұл квадраттық призма. К -  призманың графтық мінездемесі: n=2k,m=4k,g=k+2. Призма – кубтық граф.Призманың жайылымы сәйкес төбелері қабырғалармен қосылған және бір-біріне концентрлі салынған k – бұрыш.

Призма К6 және оның жайылымы

2.Антипризмалар – негізіне бір біріне қатысты араласқан екі К бұрыштылар кіретін призматойдтар.Ал шеткі жақтары үшбұрыштар болып келеді.n=2k,m=4k,g=2k+2.

Тұжырым 1.К антипризмалары - тұрақты жазық графтар.

                               4-антипризма  және оның жайылымы

3.Алтышатырлы куб. Ол қарапайым кубтан келесі жолмен алынады:Әр жақтан оның бойынан тыс нүктелер алып,табаны сол жақтар болатындай дұрыс пирамидалар сызамыз. n=14,m=36,g=24. Жазбасы үшбұрыш болатын жазық граф.

                Алтышатырлы куб және оның жайылымы

4.Ромбылық додекаэдр – бұл жақтары ромб болатын он екі жақтан тұратын граф.Табиғатта бағалы гранат минералының кристал торы түрінде кездеседі.n=14,m=24,g=12.Ромбының түріндегі жазбасы бар

                     Додекаэдр және оның жайылымы

5.Жүздік графтар – араның жүздігіне  сәйкес келетін графтар.n=13,m=21,g=10.Онда алтыбұрышты шығысы және тоғыз шеткі төртбұрышты жақтардан тұрады,сонымен қатар төрт жақтың қиылысатын үш төбе де төртінші дәрежелі, ал қалған он төбесі үшінші дәрежелі болады.

Тұжырым 2. Жүздік және гранат графтары гамильтондық емес,себебі онда гамильтондық цикл жоқ, бірақ кейбіреулерінде гамильтондық шынжыр бола алады.

Қорытынды

Платон, Архимед денелерінің және басқа да туынды денеледі қарастыра келе, Платондық және Архимедтік денелерде симметриялылық өте жоғары дәрежеде сақталады, олар тұрақты 3,4,5 ретті планарлы және гамильтондық дәрежелер көрсетеді.Олар жақтарының түріне байланысты әртүрлі жайылымдары бола алады. Жақтарының неше түрі болса, жайылымның сонша түрі болатынын дәлелденді.Жобада Платон және Архимед денелерінің жайылымдарын бере алдық.Локальді және қарапайым жолдардың  көмегімен жартылай дұрыс полиэдрлардың  құрылымы есептеледі, дұрыс полиэдрлардың  ұтымды жазылу алгоритмі берілді.Сонымен,барлық платондық денелер- тұрақты графтар: тетраэдр, куб, додекаэдр - үшінші дәрежелілер, октаэдр -  төртінші, икосаэдр -  бесінші дәрежелі.Платондық денелер қатаң тізбекте симметриялы, сондықтан олар кристаллографияда, стереохимияда кең қолданыс тапқан.Сонымен, метан молекулярлық графына тетраэдр сәйкес келеді.

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

Жүздік және гранат графтары гамильтондық емес, себебі онда гамильтондық цикл жоқ, бірақ кейбіреулерінде гамильтондық шынжыр бола алады. Осы күрделі денелердің жайылымын бірнеше түрде беруге болатыны тұжырымдалып, жайылымы  жасалып, сызбада көрсетілді. Локальді және қарапайым жолдардың  көмегімен жартылай дұрыс полиэдрлардың  құрылымы есептелді, дұрыс полиэдрлардың  ұтымды жазылу жолдары ұсынылды.

Пайдаланылған әдебиеттер тізімі:

[1]. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.Наука, 1977 г

[2]. Емельичев В. Л. Лекции по теории графов; Наука, 1990 г  

[3]. Липский В. Комбинаторика для програмистов; Мир, 1988 г

[4]. Никольский С.М.Школьная энциклопедия – математика. Дрофа, 1997 г

[5]. Оре О. Теория графов; Мир, 1968 г

[6]. Харгиттай И. Симметрия глазами химика; Мир, 1989 г

[7]. Яблонский С.В. Введение в дискретную математику.Наука, 1986 г

E1

E1

Остов группы S3