Введение в теорию графов

Укажите эйлеровы графы.

На рисунке указана схема дорог, связывающих городаABCDEGMNK.По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из городаAв городK?

Сформулируйте утверждения, подставив в прямоугольник слова по смыслу. Путём в графе от вершины А до вершины B назовём такую рёбер графа, в которой каждые соседних ребра имеют вершину. Длина пути — это рёбер в этом . Путь в графе, у которого вершины не повторяются, называется . Цикл в графе — это путь, у которого — в одной вершине, а рёбра и промежуточные вершины . Если существует путь, ведущий из одной вершины в другую, то эти вершины называются . Если в графе любые две вершины соединены, то такой граф называется . Граф, у которого каждая соединена с любой вершиной, называется . Чтобы найти количество рёбер в полном графе, у которого n вершин, нужно воспользоваться формулой:.

Выполните классификацию графов. Сопоставьте условие с заключением.

В таблице приведены расстояния между четырьмя посёлками. Если пересечение строки и столбца пусто, то между посёлками дороги нет. Постройте данный граф и с помощью него определите кратчайший путь из посёлкаAвD.

Найдите сумму степеней всех вершин графа.

На обед в школьной столовой предлагают первое блюдо — куриный суп и борщ, второе блюдо — плов, третье блюдо — компот из сухофруктов, сок. Какой граф соответствует данному условию?

В одной из вершин октаэдра сидит муха. Она может проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину. Укажите верные путь, по которому она может совершить данный маршрут.

Количество столбов в городе равно80,некоторые из них соединены кабелями, проводящими электричество. От каждого столба должно отходить по18кабелей. Сколько всего нужно кабелей?

В некотором графе5вершин, степени которых равны:12; 5; 14; 10; 9. Сколько в этом графе рёбер?

При каких условиях можно построить эйлеровы графы? Выберите верные утверждения.

Дан граф. Сопоставьте условие с заключением.

Антон решил пригласить друзей — одноклассников на день рождение. Известно, что Антон дружит с Ильёй и Николаем, Дмитрий дружит с Ильёй и Алексеем, Марина дружит с Жанной и Максимом, Яна дружит с Максимом. Может ли Антон пригласить Максима на день рождения?

У Юры с Антоном вышел спор. Юра утверждает, что из проволоки длиной8 м нельзя сложить каркас куба при условии, что нельзя резать проволоку и делать рёбра разной толщины, а Антон говорит, что можно. Кто из ребят прав? Решите данную задачу, вставив в прямоугольник слова по смыслу. Каркас куба можно представить в виде графа. Данное условие говорит о том, что нельзя проволоку и делать рёбра разной . Данный граф нужно , не отрывая карандаша от бумаги, значит, этот граф является . Эйлеров может иметь либо нечётные вершины, либо не иметь их . Но у графа на рисунке все вершин нечётные, значит, этот граф эйлеровым. А значит, куб из проволоки длиной м сложить не получится. Выходит, что прав .