Билеты по Дискретной математике «Теория Графов»



Скачать 12.79 Kb.
Дата08.10.2012
Размер12.79 Kb.
ТипДокументы
Билеты по Дискретной математике «Теория Графов».


  1. Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов.

  2. Подграф. Частичный граф, подграф. Полные, пустые и двудольные подграфы.

  3. Способы задания графов (орграфов). Изоморфизм графов.

  4. Операции над графами.

  5. Степень вершины, графа. Свойства распределения вершин графа.

  6. Цепь: составная, сложная, простая. Длина цепи. Метрика. Расстояние между вершинами в графе. Диаметр в графе.

  7. Связность графа. Вершинная и реберная связность. Компонента связности графа. Нахождение компоненты связности.

  8. Связность в орграфах. Компонента сильной связности (КСС). Нахождение КСС. Конденсат графа.

  9. Циклы в графе. Эйлеров и Гамильтонов циклы / графы. Критерий эйлеровости графа.

  10. Пространство циклов графа. Цикломатическая матрица. Цикломатический базис. Цикломатическое число. Алгоритм порождения циклов.

  11. Разделяющее множество. Разрез графа. Ко-циклический ранг графа. Поиск базисной системы разрезов графа.

  12. Внутренняя устойчивость графа. Пустой подграф. Число внутренней устойчивости. Алгоритм порождения пустых подграфов.

  13. Полный граф. Полные подграфы. Плотность графа. Алгоритм порождения полных подграфов.

  14. Внешняя устойчивость графа. Положительная и отрицательная внешняя устойчивость орграфа.

  15. Раскраска графа. Хроматическое число. Алгоритм нахождения хроматического числа и раскраски графа.

  16. Оценки хроматического числа. Приближенная раскраска (оценка по Ершову). Значение (оценка) хроматического числа для операций над графами.

  17. Реберные графы. Критерий свойства реберности. Нахождение образа реберного графа.

  18. Группа подстановок. Свойства группы. Вычисление произведения подстановок.

  19. Автоморфизм и группа автоморфизмов графа.


Похожие:

Билеты по Дискретной математике «Теория Графов» iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Билеты по Дискретной математике «Теория Графов» iconПрограмма дисциплины «избранные главы теории графов»
...
Билеты по Дискретной математике «Теория Графов» iconРабочая программа по дисциплине «Дискретная математика»
Охватывает лишь минимальное число необходимых понятий из таких разделов дискретной математики, как теория множеств, теория графов,...
Билеты по Дискретной математике «Теория Графов» iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Билеты по Дискретной математике «Теория Графов» iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Билеты по Дискретной математике «Теория Графов» iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Билеты по Дискретной математике «Теория Графов» iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Билеты по Дискретной математике «Теория Графов» iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Билеты по Дискретной математике «Теория Графов» iconЛекции по теории графов. М.: Наука, 1990 Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005
Государственного экзамена по информатике на математическом факультете мпгу по специальностям «Информатика» и «Информатика» с дополнительной...
Билеты по Дискретной математике «Теория Графов» iconНаучная работа по теме: 1 глава 1 4 теория графов 4 Эйлеровы графы 7 Задача о мостах, Леонард Эйлер и теория графов 8
Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась...
Разместите кнопку на своём сайте:
ru.convdocs.org


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