Начать. Это бесплатно
или регистрация c помощью Вашего email-адреса
Графы создатель Mind Map: Графы

1. Матрица инцидентности - столбцы матрицы соответствуют ребрам, строки — вершинам.

2. Матрица смежности - это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.

3. 1. Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине. 2. Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. 3. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком. 4. Число нечетных вершин графа всегда четное. 5. Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф будет равно половине числа нечетных вершин этого графа.

4. Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

5. Виды

5.1. Ориентированный

5.1.1. Граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами.

5.2. Неориентированный

5.2.1. Граф, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

5.3. Граф-дерево

5.3.1. Граф, соединяющий вершины, без какого-либо цикла.

5.4. Эйлеровый

5.4.1. Граф, проходящий по всем рёбрам графа и притом только по одному разу.

6. Область применения

6.1. Программирование

6.1.1. Схемотехника

6.2. Экономика

6.2.1. Социлогия

6.2.1.1. Химия

7. Свойства

8. Способы представления

9. История