Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
13 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
424.65 kB
Просмотров:
71
Скачиваний:
2
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Эйлеров граф Эйлеров цикл,](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img0.jpg)
Содержание слайда: Эйлеров граф
(Эйлеров цикл, Эйлеров путь)
№2 слайд![Можно ли не отрывая руки](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img1.jpg)
Содержание слайда: Можно ли не отрывая руки нарисовать?
№3 слайд![](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img2.jpg)
№4 слайд![Свойства вершин Эйлерова графа](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img3.jpg)
Содержание слайда: Свойства вершин Эйлерова графа
№5 слайд![-ое свойство Эйлеровых графов](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img4.jpg)
Содержание слайда: 1-ое свойство Эйлеровых графов
В Эйлеровом графе число вершин с нечетной степенью равно 0 (условие существования эйлерова цикла)
В полуэйлеровом графе число вершин с нечетной степенью равно 2 (условие существования эйлерова пути в графе)
№6 слайд![Наши примеры](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img5.jpg)
Содержание слайда: Наши примеры
№7 слайд![Структура данных int i,j, n,](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img6.jpg)
Содержание слайда: Структура данных
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 слайд![Подсчет степеней for i i lt n](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img7.jpg)
Содержание слайда: Подсчет степеней
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 слайд![Выполнение первого свойства](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img8.jpg)
Содержание слайда: Выполнение первого свойства
if (k==0) cout << “возможно эйлеров цикл”;
else if (k==2) cout << “возможно эйлеров путь”;
else {
cout << “не эйлеров граф”;
return 0;
}
№10 слайд![-ое свойство связанность графа](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img9.jpg)
Содержание слайда: 2-ое свойство – связанность графа
№11 слайд![-е свойство связанности int Q](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img10.jpg)
Содержание слайда: 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 слайд![-ое свойство связанности int](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img11.jpg)
Содержание слайда: 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 слайд![-ое свойство связанности Int](/documents_6/7a80aae75d5a25d40f3a0dd5f228002f/img12.jpg)
Содержание слайда: 2-ое свойство связанности
Int z=0; //число нерасмотренных
// островов с мостами
for ( int i=1; i<=n; i++)
z+=Q[i];
if (z>0) cout << “Не эйлеров граф”;
else if (k==0) cout << “Эйлеров граф”;
else cout << “Полуэйлеров граф”;