Как посчитать ребра графа

Полный граф

K7 , полный граф с 7 вершинами
Вершин n
Рёбер n ( n − 1 ) 2 <displaystyle <frac <2>>>
Диаметр 1
Автоморфизмы n! (Sn)
Хроматическое число n
Хроматический индекс n если n — нечётное,
иначе n − 1
Обозначение Kn
Медиафайлы на Викискладе

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с n <displaystyle n> вершинами имеет n ( n − 1 ) / 2 <displaystyle n(n-1)/2> рёбер и обозначается K n <displaystyle K_> . Является регулярным графом степени n − 1 <displaystyle n-1> .

Полный граф образуется из вершин и ребер (n-1)-симплекса.

По́лный ориенти́рованный граф — ориентированный граф, в котором каждая пара различных вершин соединена парой дуг (с различными направлениями).

Графы с K 1 <displaystyle K_<1>> по K 4 <displaystyle K_<4>> являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф K 5 <displaystyle K_<5>> и, следовательно, не удовлетворяют критерию Понтрягина-Куратовского.

Примеры [ править | править код ]

Ниже приведены полные графы с числом вершин от 1 до 12 и количества их рёбер.

Введение

Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.

Понятие графа

Рассмотрим две задачи.

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

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.

Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например.если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Степени вершин и подсчет числа ребер графа

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

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

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

Читайте также:  Как передать видео на айпад

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

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:

Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Графы Эйлера

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Читайте также:  Как откатиться на виндовс 10

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

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

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3×3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Рис. 1 Рис. 2

Решение. Занумеруем клетки доски, как показано на рисунке:

Каждой клетке поставим в соответствие точку на плоскости и, если из одной клетки можно попасть в другую ходом шахматного коня, то соответствующие точки соединим линией. Исходная и требуемая расстановки коней показаны на рисунках:

При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно.

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9372 — | 7304 — или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Класс: 7

Презентация к уроку

Загрузить презентацию (486,9 кБ)

Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.

Профиль класса: общеобразовательный.

Тип урока: изучение и первичное закрепление новых знаний.

Знания и умения учащихся:

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

Образовательные:

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

Развивающие:

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

Воспитательная:

  • воспитывать культуру общения на уроке, взаимоуважение.

План урока

  1. Организационный момент (приветствие класса, подготовка к уроку, проверка домашнего задания, включающая повторение материала предыдущего урока);
  2. Теоретический материал (знакомство с темой предстоящего урока, объяснение нового материала и краткая запись в рабочую тетрадь новых теоретических сведений по теме урока);
  3. Закрепление материала (решение задач);
  4. Итоги урока (краткий вывод и домашнее задание).
Читайте также:  Как обновить по для телевизора philips

Давайте вспомним основные понятия теории графов. Для этого проведем разминку по типу незаконченного предложения (Презентация, сл.: 2, 3, 4). Каждый ученик имеет карточки с пропущенными словами в предложение. Учитель зачитывает предложение, останавливаясь перед пропущенным словом, и выбирает ученика, который в свою очередь должен поднять карточку. Далее этот ученик читает дальше предложение, также останавливаясь перед пропущенным словом, и уже сам выбирает одноклассника для ответа и т. д. по цепочке.

Проверим в классе решение домашней задачи (Презентация, сл.: 5, 6, 7). Один ученик выходит к доске и рисует граф. Далее мы вместе проверяем ребра (дороги между городами), считаем количество выходящих ребер из каждой вершины и смотрим связи между городами.

Сегодня на уроке мы продолжим изучение графов, познакомимся с понятием “степень вершины графа” и сформулируем определение связности графа (обратим внимание на наш граф из домашнего задания и определим, является ли он связным или нет и почему). Рассмотрим утверждение о количестве ребер графа, и проверим в соответствие с этим утверждением, правильно ли мы посчитали количество ребер графа в домашней задаче. И рассмотрим теорему о четности числа нечетных вершин графа.

Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для петли будем считать, что это ребро выходит из вершины дважды (Презентация, сл. 8).

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

Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной (Презентация, сл. 9).

Запишем определение в тетрадь и перечислим через запятую сначала четные вершины, а потом нечетные вершины для уже нарисованного графа. Проверим задание вслух.

Количество ребер графа равно половине суммы степеней его вершин. Пусть граф имеет n вершин, тогда число ребер равно:

(Презентация, сл. 10)

Запишем утверждение в рабочую тетрадь и посчитаем количество ребер графа в домашней задачке. Проверим ответ в классе. Рассмотрим задачу и ее решение на подсчет числа ребер графа без построения. (Презентация, сл. 11).

Сформулируем теорему о количестве вершин нечетной степени любого графа и запишем формулировку в рабочую тетрадь. (Презентация, сл. 12).

Теорема. Количество вершин нечетной степени любого графа всегда четно.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин.

Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной.

А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Разберем доказательство и проверим теорему на нашей домашней задачке.

Рассмотрим несколько задач.

Задача. В государстве 50 городов, из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих дорог из городов: 50 * 4 = 200. Однако, мы понимаем, что при подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 100.

Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Ответ. Нет (теорема о четности числа нечетных вершин).

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

В качестве домашнего задания ученики получать карточки с тремя задачами (Презентация, сл. 13).

Adblock detector