Ойлер графики

Simonenko EA Дискретна математика. лекции

Euler цикъл е цикъл, който преминава на всеки ръб на графиката точно веднъж. Съответно, графиката съдържа цикъл, наречен Ойлер. Формулиране критерий Ойлеров графика:

Теорема (Ойлер, 1736.). Свързана ненасочена графика съдържа Ойлеров цикъл, ако и само ако нечетен брой върхове на степен нула.

За насочено графика формулировка на теоремата е малко по-различен: насочен графика има цикъл Ойлер ако и само ако той е свързан и степента на всеки връх е равна на входното ниво на изхода си.

Ако не съществува Ойлер цикъл на графиката, това означава, че от следващата по този цикъл, е възможно да се направи графика на хартия, без да вдигате молива от нея.

Да предположим, че са дадени ненасочена графика G, задоволяващи Теорема на Ойлер. Помислете за намиране на алгоритъм Eulerian цикъл в тази графика. Този алгоритъм се основава на прекосяване на графиката в дълбочина. При прехода към следващото върха ще премахне съответното изминато ребро. При констатиране на върхове, от които ребрата не вървят (ние ги премахнат в началото на преминаващи дълбочина), ще запише номера му в стека. върхове откриване с нулеви ръбове предполага, че намерих цикъл. Тя може да бъде отстранен, и паритета връх градуса няма да се промени. Процесът продължава, докато има не пресечени ръбове. След края на цялата графика прекосява в дълбочина брой върхове да се съхранява в купчина от порядъка на цикъл Ойлер.

Вход. Брой Графика, за която се близост матрица; върха на стека стека Ойлер номер цикъл започне връх U.

За всички графиката върховете V Графика, съседен U: Графика [U, V]: = 0, Графика [V, U]: = 0; DFS (Графика, Stack, V).

Със задачата за намиране Hamiltonian цикли са тясно свързани с проблема за търговския пътник (а амбулантен търговец). Формулиран го по този начин: има N градове, са известни разстояния между тях. Merchant ще посети всички градове н точно веднъж, връщайки се към тази, от която започва пътуването си. Задължително да се намери начин за търговския пътник с минимална обща дължина.

Фигура 3: Пример tetagrafa

Simonenko EA Дискретна математика. лекции

планарни графики

Казват, че графиката се поставя върху всяка повърхност, ако може да бъде съставен от тази повърхност без преминаване ръбове. Ако графиката може да бъде поставен в равнина, графика, се нарича планарна. Граф положи върху плоска равнина, наречена.

В зоната, ограничена от краищата на планарна графика и не съдържат други върхове и ръбове на графиката, наречена лице. Външната част на самолета по отношение на графиката също се считат за лице. Броят на плоските повърхности на G е означен с R (G).

Теорема (формула Ойлер). В свързан планарна графика G = (В. Е) равенство п - т + р = 2. където п = V. m = Е и R = R (G).

Ако G - свързан планарна графика, п> 3. 3 след м п - 6. В действителност, всяка страна е ограничен от най-малко три ръбове, и всеки ръб граници не повече от две лица следователно R 3 2 m. От това и от формула Ойлер: = 2 п - т + р п - т + 2 m / 3. Следва: 3 п - 3 м + 2 m 6 m 3 п - 6.

Нека покажем, че K 5 и К 3,3 не е една и съща равнина. За графиката К 5 имаме п = 5 и m = 5, 4/2 = 10 замествайки п и т в неравенството 10 3 5-10 9 юни Това противоречие графика К 5 не може да бъде равнинна.

Фигура 4: K5 графиките и K3,3

За графиката K 3,3 има п = m = 6 и 9. В тази графика не "триъгълници", така че при полагане на равнината на всяка страна е ограничен от най-малко четири ръбове и, следователно, 4R 2 R m т2. Според формула Ойлер: 6-9 + R = R 2 = R 5. Заместването в неравенството: 05 Февруари 10 09 сеп противоречие.

Planar графика, в която всички аспекти, включително и чуждестранни, са триъгълници, наречени

равнинна триангулация. Максимална плосък графика е графика, която престава да бъде фиксирана с добавянето на всеки край.

Теорема. Брой Count е максимумът, плосък, ако и само ако това е равнинна триангулация.

За всеки максимална планарна графика, М равенство = 3, п - 6.

Корица и независимост

Те казват, че връх на графиката обхваща за инцидента на ребрата й, и един ръб инцидент, за да го покрива горната част. Това повдига два проблема: 1) търсене на минималния брой върхове, обхващащи всички краища на графиката G (покритие на брой връх 0 α (G)); 2) намери минималния брой ръбове, обхваща всички върховете на G (броят на крайбрежната покритие

За пълна графика K N:

α 0 (К н) = N - 1. α 1 (К н) = [N 2]. (Когато [] означава "таван").

Наборът от върховете на графика G се нарича независима. ако не два върха в комплекта не са в съседство. Най-голям броят на върховете в независим набор се нарича

номер връх независимост β 0 (G). и съответно множество от най-големите. Наборът от не-съседни ръбове на графика G се нарича независими. Най-голям брой ръбове на независим набор от линия номер наречени независимост β 1 (G).

За пълна графика K N:

α 0 (К н) = N - 1. β 1 (К н) = [N 2]. (Когато [] означава "етаж").

Теорема. За всяка графика без изолирани върховете равенства:

а 0 + β 0 = п = а + 1 β 1.