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

1. Виды

1.1. Ориентированные - графы, рёбрам которых присвоено направление

1.2. Неориентированные - множество вершин и набор рёбер, то есть соединений между парами вершин

1.3. Дерево - граф, в котором каждое ребро это мост

1.4. Полный - граф, в котором каждая пара различных вершин смежна

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

2.1. Химия

2.2. Электротехника

2.3. Экономика

2.4. Информатика

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

3.1. Матрица инцидентности - в ней указываются связи между ребрами) и вершинами. Столбцы матрицы соответствуют ребрам, строки — вершинам

3.2. Матрица смежности - это квадратная матрица размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину

4. Свойства

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

5. История

5.1. Впервые основы теории графов появились в работах Леонарда Эйлера, в которых он описывал решение головоломок и математических развлекательных задач. Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга