Графы

Пример

Пример:
Можно описывать сеть дорог как набор перекрёстков, некоторые из которых соединены участками дорог.

На этой картинке имеется ряд языков, на которых говорили или говорят некоторые народы Европы. Учёные-лингвисты давали на такой схеме общего предка нескольким языкам, если они считали, что эти несколько языков родственны, т.е. когда-то в прошлом были одним языком, а потом накопили достаточно различий и стали отдельными языками.

В графе цепи питания биологические виды являются вершинами, и направленное ребро проведено от одного вида к другому тогда, когда первый вид является пищей для второго.

Степень:
Пример:
Входящие: deq + (V)= 3 ; Исходящие: deg – (V) = 3 Степень петли : deg (V) = 2 –всегда!!!

Дерево

Дерево

Задачи

Задача
№ 3 В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.

Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?
Решение:

Задача 2.
На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Задача №5.
В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?[12]
Решение:
Построим граф. Сыгранные игры отметим синими линиями, красными дополним до полного графа. Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).

Деревья обладают рядом особых свойств.
Например, в дереве между любыми двумя вершинами существует единственный простой путь
V - количество вершин (от англ. vertex «вершина»),
E — количество рёбер (от англ. edge «ребро»
Например:
Например, у дерева на рисунке :
V = 11, E = 10. Мы видим, что для графа на рисунке E = V − 1.

Задача 2
Сколько различных обедов П.И. Чичиков мог насчитать из блюд, выставленных на столе у П.П. Петуха, если бы на каждый обед выбирать только одно холодное блюдо, одно первое блюдо и одно второе блюдо? На столе у П.П. Петуха на этот раз были выставлены из холодных блюд
студень с хреном, свежая икра, свеже просоленная белужина;
на первое - уха из стерлядей, щи с грибами;
на второе - осетрина жареная, теленок, жаренный на вертеле.