Презентация: Эйлеров граф (Эйлеров цикл, Эйлеров путь)

Эйлеров граф (Эйлеров цикл, Эйлеров путь) Можно ли не отрывая руки нарисовать? Эйлеров граф (Эйлеров цикл, Эйлеров путь) Свойства вершин Эйлерова графа 1 - ое свойство Эйлеровых графов Наши примеры Структура данных Подсчет степеней Выполнение первого свойства 2-ое свойство – связанность графа 2-е свойство связанности 2-ое свойство связанности 2-ое свойство связанности
1/13
Средняя оценка: 5.0/5 (всего оценок: 56)
Скачать (424 Кб)
Код скопирован в буфер обмена
1

Первый слайд презентации: Эйлеров граф (Эйлеров цикл, Эйлеров путь)

Старший преподаватель к афедры теоретической кибернетики Хадиев Р.М. КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

2

Слайд 2: Можно ли не отрывая руки нарисовать?

3

Слайд 3

4

Слайд 4: Свойства вершин Эйлерова графа

5

Слайд 5: 1 - ое свойство Эйлеровых графов

В Эйлеровом графе число вершин с нечетной степенью равно 0 (условие существования эйлерова цикла) В полуэйлеровом графе число вершин с нечетной степенью равно 2 (условие существования эйлерова пути в графе)

6

Слайд 6: Наши примеры

Эйлеров цикл Эйлеров путь

7

Слайд 7: Структура данных

int i,j, n, // число вершин G[100][100], //G[ i ][j]=1 – наличие моста R[100], // степень вершины – число мостов cin >> n; // ввод данных for ( i =1;i<=n; i ++) for (j=1;j<=n; j ++ ) cin >> G[ i ][j]

8

Слайд 8: Подсчет степеней

for ( i =1;i<= n;i ++) { R[ i ]=0; for (j=1;j<= n;j ++) R[ i ]+=G[ i ][j]; } int k=0; // число вершин с нечетной степенью for ( i =1;i<= n;i ++) k+=R[ i ] %2 ;

9

Слайд 9: Выполнение первого свойства

if (k==0) cout << “ возможно эйлеров цикл ” ; else if (k==2) cout << “ возможно эйлеров путь ” ; else { cout << “ не эйлеров граф ” ; return 0; }

10

Слайд 10: 2-ое свойство – связанность графа

Пример не эйлерова графа с четными степенями вершин, но не связанного.

11

Слайд 11: 2-е свойство связанности

int Q[100] = {1}; // Выявление компонент // связанности (КС). 1 – не связанная вершина for ( i =1;i<= n;i ++) if (R[ i ]==0) Q[ i ]=0; // изолированная вершина i =1; while (Q[ i ]==0 & i <=n) i ++; if ( i >n) { cout << “ вырожденный граф ”; return 0;}

12

Слайд 12: 2-ое свойство связанности

int p[100], m=1; // число элементов КС a=1; // анализируемый элемент КС P[1]= i ; // первый элемент КС while (a<=m) { for ( i =1;i<= n;i ++) if (Q[ i ]==1 & G[ i ][P[a]]==1) { m++; // включение i в компоненту свсязанности P[m]= i ; Q[ i ]=0; // исключение i из дальнейшего рассмотрения } a++; // переход }

13

Последний слайд презентации: 2-ое свойство связанности

Int z=0; // число нерасмотренных // островов с мостами f or ( int i =1; i <=n; i ++) z+=Q[ i ]; if (z>0) cout << “ Не эйлеров граф ”; else if (k==0) cout << “ Эйлеров граф ”; else cout << “ Полуэйлеров граф ”;

Похожие презентации

Ничего не найдено