графы

Построить конверт не отрывая карандаша от бумаги и не проводя по одной линии дважды

Леонард Эйлер ( ) математик, механик, физик и астроном. По происхождению швейцарец. Автор свыше 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и других, оказавших значительное влияние на развитие науки.

На рисунке изображена схема мостов города Кенигсберга. Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

граф конечная совокупность точек, называемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа. неориентированный графориентированный граф

Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной. Если среди вершин графа больше двух нечетных вершин, то этот граф можно обойти, а если меньше двух – нельзя. При наличии двух нечетных вершин обход следует начинать в одной из них, а заканчивать в другой. У графа не может быть ровно одной нечетной вершины, а если у него нет нечетных вершин, то обход можно начинать с любой вершины и в ней же заканчивать

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ? Теорема: В любом графе четное число нечетных вершин

Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер Являются ли данные графы связными?

Одинаковые или разные графы?

Любой ли граф можно изобразить на плоскости, чтобы его ребра не пересекались?

Графы, которые можно построить на плоскости без пересечения их ребер, принято называть плоскими. Если граф не плоский, то в нем «сидит» ил граф «домики-колодцы» или «полный пятивершинник». Для плоских графов В – количество вершин, Р – ребер, Г – граней В-Р+Г=2 В-Р+Г=1 Для выпуклого многогранника

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Г В А К Е Б Д Ж И

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Г В А Д З Б Е Ж И К

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З? А Б В Г Д Е Ж З

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? А Б В Г Е К З Ж Д И

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? А Б В Г Е К З Ж Д И

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Г В А К Е Б Д Ж И З

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И? Г В А И Е Б Д Ж З