Лекции по теории графов. М.: Наука, 1990. Берж К. Теория графов и ее применения. М.: Изд иностр лит., 1962



Скачать 31.96 Kb.
Дата11.10.2012
Размер31.96 Kb.
ТипЛекции

ТЕОРИЯ КОНЕЧНЫХ ГРАФОВ И ЕЕ ПРИЛОЖЕНИЯ



ОСНОВНАЯ ЛИТЕРАТУРА

  1. Харари Ф. Теория графов. – М.: Мир, 1973.

  2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

  3. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.

  4. Берж К. Теория графов и ее применения. – М.: Изд. иностр. лит., 1962.


ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА

  1. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1977.

  2. Евстигнеев В.А. Применение теории графов в программировании. - М.: Наука, 1985.



Примеры приложений теории графов.

1. Транспортные задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и/или другие транспортные маршруты (например, авиационные). Сюда же можно отнести и модели сетей снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называют задачами обеспечения или задачами о грузоперевозках.

2. Технологические задачи, в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги (т.е. ребра, в которых пары вершин упорядоченные) – потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и потоков, обеспечивающих эту загрузку.

3. Модели организационных структур, в которых вершинами являются элементы организационной системы, а ребрами или дугами – связи (информационные, управляющие, технологические и др.) между ними. Примерами моделей оргструктур являются компьютерные программы, управление проектом строительства некоторого объекта. В рамках таких моделей решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

4. Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения согласованности взаимодействия между представителями группы и др.
Занятие 1. Способы задания графов. Основная теорема теории графов.

1. Даны графы G и H:

а) Составьте для каждого из них списки вершин и ребер (в виде таблицы), а также матрицы смежности, инцидентности, векторов смежности.
Определите по этим матрицам минимальную, максимальную и среднюю степени вершин данных графов.

б) Из матрицы смежности для данных графов получите аналогичные матрицы для дополнений к этим графам, и по ним восстановите графы и .







G: H:

2. По матрице инцидентности определите минимальную, максимальную и среднюю степени вершин графа G. Не изображая этот граф в виде диаграммы, составьте список его вершин и ребер, а также матрицы смежности и векторов смежности.

x1 x2 x3 x4 x5 x6 x7



3. N шахматистов (N2) проводят турнир в один круг (каждый из участников должен сыграть с каждым по одному разу). Докажите, что в любой момент найдутся двое, закончившие одинаковое число партий.

4. N человек (N>2) проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что либо в точности один участник еще не сыграл ни одной партии, либо ровно один сыграл все партии.

5. Существуют ли графы со следующими наборами степеней вершин:

а) {2, 3, 3, 2, 3}; б) {1, 2, 3, 4} ?

Если существуют, то изобразите их графически.

6. Сколько рёбер имеет полный граф с p вершинами?

7. Сколько рёбер имеет регулярный граф с p вершинами степени r?

8. Сколько рёбер может быть у регулярного графа с 9 вершинами?

9. Докажите, что каждый кубический граф имеет чётное число вершин.

10. Сколько вершин может быть у графа с 4 ребрами, если петли, кратные ребра и изолированные вершины у него отсутствуют?




Похожие:

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


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