Алгоритм Зыкова



Скачать 14.91 Kb.
Дата04.07.2013
Размер14.91 Kb.
ТипДокументы
Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный граф. Матрицы смежностей и инциденций. Изоморфизм графов.
Путь в графе и связные компоненты графа. Цепи, простые цепи, циклы, простые циклы. Операции удаления вершины, удаления ребра, подразбиения ребра. Дерево и его особенности.
Эйлеров цикл и эйлеров граф. Условия существования эйлерова цикла. Задача о разбиении графа на минимальное число цепей.
Гамильтонов цикл и гамильтонов граф. Условия Дирака, Оре и Поша, гарантирующие существование в графе гамильтонова цикла.
Планарные и плоские графы. Формулировки теоремы Эйлера о соотношении чисел граней, ребер и вершин плоского графа.
Раскраска графа. Формулировка теоремы о пяти красках. Хроматическое число и Зыкова вычисления хроматического многочлена графа.
Алгоритм Зыкова.
Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда построения кратчайших маршрутов.
Ориентированный граф и его графическая интерпретация. Локальные степени. Матрица смежностей. Ориентированные пути и связность в ориентированном графе.
Доказать, что любой граф содержит четное число вершин нечетной степени.
Пусть G - граф с n вершинами и k компонентами. Доказать, что число m его ребер удовлетворяет неравенствам:


Доказать, что если степень каждой вершины графа G(V,E) не меньше двух, то G содержит цикл.
Доказать, что для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины.
Доказать, что связный граф G является эйлеровым тогда и только тогда, когда ка­ждая вершина G имеет четную степень.
Доказать, что связный граф G является полуэйлеровым тогда и только тогда, когда в нем существует точно две вершины нечетной степени.

Доказать, что граф G(V, E) имеет остовное дерево тогда и только тогда, когда он связен.

Метод ветвей и границ

Похожие:

Алгоритм Зыкова iconТеатр николая зыкова мастерская чудес
Утренняя почта", "Что? Где? Когда?", " До шестнадцати и старше", "Аншлаг", "Смехопанорама", "Смеяться разрешается", "Истории в деталях"...
Алгоритм Зыкова iconТеатр николая зыкова кукольный карнавал
Утренняя почта", "Что? Где? Когда?", " До шестнадцати и старше", "Аншлаг", "Смехопанорама", "Смеяться разрешается", "Истории в деталях"...
Алгоритм Зыкова iconТеатр николая зыкова динозавр и его компания
Утренняя почта", "Что? Где? Когда?", " До шестнадцати и старше", "Аншлаг", "Смехопанорама", "Смеяться разрешается", "Истории в деталях"...
Алгоритм Зыкова iconТеатр николая зыкова куклы, XXI век
Утренняя почта", "Что? Где? Когда?", " До шестнадцати и старше", "Аншлаг", "Смехопанорама", "Смеяться разрешается", "Истории в деталях"...
Алгоритм Зыкова iconПонятие алгоритма
Ом в III веке до нашей эры алгоритм нахождения наибольшего общего де­лителя двух чисел (алгоритм Евклида). Вплоть до начала XX века...
Алгоритм Зыкова icon«Циклические алгоритмы. Алгоритм Евклида»
Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (нод) двух целых неотрицательных чисел
Алгоритм Зыкова iconВолновой алгоритм (Алгоритм Ли)
Волновой алгоритм является одним из самых уникальных алгоритмов трассировки. Он позволяет построить трассу (путь) между двумя элементами...
Алгоритм Зыкова iconАлгоритм (Делай раз, делай два)
Обеспечить понимание учащимися терминов «информатика», «информация», «компьютер», «алгоритм», «команда алгоритма». Систематизировать...
Алгоритм Зыкова iconСлово «алгоритм»: происхождение и развитие Слово «алгоритм»
Слово «алгоритм» происходит от имени великого среднеазиатского учёного Мухаммеда аль-Хорезми́, жившего в первой половине IX ве́ка...
Алгоритм Зыкова iconПрактическая работа №1 «Сравнение трактовок понятий алгоритм» Информационный модуль
«алгоритм» своим происхождением обязан великому ученому средневековья, имя которого Мухаммед ибн Мусса аль-Хорезми (753-850). Алгоритм...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org