Полный граф у которого 6 вершин

Полный граф у которого 6 вершин

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

Определение. Связный граф без циклов (замкнутых путей) называется деревом.

1. Докажите, что в любом дереве число вершин на единицу больше числа рёбер. 2. Докажите, что из любого связного графа можно удалить часть рёбер так, что останется дерево.

Определение. Полным графом называется граф, в котором любые две вершины соединены ребром. Полный граф с n вершинами обозначается K n .

3. Сколько рёбер в графе K n ? Определение. Граф называется плоским (планарным), если его можно изобразить на плоскости так, чтобы рёбра не пересекались. 4. Планарен ли граф K 4 ? Обозначения. Пусть дан граф на плоскости. Тогда В — число вершин, Р — число рёбер, а Г — число граней, т.е. частей, на которые рёбра графа разбивают плоскость. 5. Докажите формулу Эйлера для связного графа на плоскости: В − Р + Г = 2. 6. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников? 7. Докажите, что а) для связного графа на плоскости 2Р ≥ 3Г, б) для связного графа на плоскости Р ≤ 3В − 6, в) последнее неравенство верно для произвольного графа на плоскости. [Во всех пунктах предполагается, что у графа хотя бы три вершины (В ≥ 3). В вырожденных случаях K 1 и K 2 эти неравенства неверны.] 8. Докажите, что граф K 5 не является планарным. 9. Есть три домика и три колодца. Можно ли соединить каждый домик с каждым колодцем тропинкой так, чтобы тропинки не пересекались?

Граф, возникающий в задаче 9, называется K 3,3 . Графы K 5 и K 3,3 в некотором смысле исчерпывают все возможные непланарные графы. А именно, верна теорема Понтрягина – Куратовского: граф не является планарным тогда и только тогда, когда он содержит в качестве подграфа или K 5 , или K 3,3 , возможно, с дополнительными вершинами на рёбрах. 10. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо „красный“, либо „синий“ граф не является плоским. Определение.Степенью вершины графа называется количество входящих в неё рёбер. 11. Докажите, что в плоском графе есть вершина, степень которой не превосходит 5. 12. Докажите теорему о пяти красках: вершины любого плоского графа можно раскрасить в не более, чем 5 цветов так, что любые две соединённые ребром вершины будут разного цвета. Верна более сильная теорема о четырёх красках. Её доказали К. Аппель и В. Хакен при помощи ЭВМ в 1976 году.

• ЗАДАЧИ
• 9-11 классы
• Комбинаторика
• Геометрия на клетчатой бумаге
• Теорема Больяи — Гервина
• Геометрические задачи на максимум и минимум
• Игры
• Правильные паркеты
• Графы
• Графы-2
• Матбой

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!

Основные определения теории графов

В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math] , называется петлей (англ. loop).

Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math] , называются смежными (англ. adjacent).

Если имеется ребро [math] (v, u) \in E [/math] , то говорят:

• [math] v [/math] — предок (англ. direct predecessor) [math] u [/math] .
• [math] u [/math] и [math] v [/math] — смежные.
• Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math] .
• Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math] .

Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math] -графом. [math] (1, 0) [/math] -граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,~v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math] . Поэтому часто используют другое определение.

Определение:

Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname, \operatorname)[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname, \operatorname : E \rightarrow V[/math] .

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Плоские графы

Определение 1. Граф G ( X , T ) называется плоским, если его можно изобразить на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины. Чертеж графа, на котором никакие два ребра не пересекаются, называют плоским представлением графа.

Примерами плоских графов могут служить простые циклы, деревья, лес и т.д.

Пример 1. Дан граф

Его плоским представлением является граф

Плоское представление имеет только плоский граф, и обратно: у всякого плоского графа всегда найдется плоское представление.

Любые попытки начертить его плоское представление обречены на неудачу.

Определение 3. Часть плоскости, расположенная вне плоского представления графа и ограниченная изнутри простым циклом, называется бесконечной гранью.

Определение 4. Две грани называются соседними, если их границы имеют хотя бы одно общее ребро.

Данный граф имеет четыре обычные грани, ограниченные циклами ( x ₁ , x ₂ , x ₆ , x ₁ ), ( x ₅ , x ₆ , x ₇ , x ₅ ), ( x ₂ , x ₃ , x ₄ , x ₅ , x ₂ ), ( x ₂ , x ₅ , x ₇ , x ₆ , x ₂ ), и одну бесконечную грань, ограниченную циклом ( x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ , x ₁ ). Грани ( x ₁ , x ₂ , x ₆ , x ₁ ) и ( x ₂ , x ₅ , x ₇ , x ₆ , x ₂ ) являются соседними, а грани ( x ₁ , x ₂ , x ₆ , x ₁ ) и ( x ₂ , x ₃ , x ₄ , x ₅ , x ₂ ) соседними не являются. Часть плоскости, ограниченная простым циклом ( x ₂ , x ₅ , x ₆ , x ₂ ), не является гранью, так как содержит внутри себя цикл ( x ₅ , x ₆ , x ₇ , x ₅ ).

В данном графе часть плоскости, ограниченная простым циклом ( x ₁ , x ₂ , x ₃ , x ₄ , x ₁ ), является гранью, так как ребро ( x ₁ , x ₅ ), расположенное внутри грани, не является циклом.

Часть плоскости, заключенная между циклами ( x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₁ ) и ( x ₆ , x ₇ , x ₈ , x ₆ ), не является гранью, так как она содержит внутри себя цикл и к тому же она не ограничена циклом. Ребро ( x ₁ , x ₆ ) является мостом, соединяющим два цикла.

Данный граф не имеет бесконечной грани, так как она не ограничена изнутри простым циклом. Мост ( x ₁ , x ₂ ) является перегородкой.

В плоском представлении дерева за грань принимают всю плоскость чертежа.

Для всякого плоского графа без перегородок число вершин n , число ребер m и число граней с учетом бесконечной g связаны соотношением n — m + g = 2, которое называется формулой Эйлера.

Определение 6. Плоский граф G ( X , T ) называется максимально плоским, или триангулированным, если к нему невозможно добавить ни одного ребра так, чтобы полученный граф был плоским.

Пример 6 . Рассмотрим граф

Данный граф можно сделать максимально плоским:

Каждая грань в плоском представлении максимально плоского графа имеет три вершины.

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

Теорема. Для любого плоского графа G ( X , T ) существует плоское представление, в котором все ребра — прямолинейные отрезки.

Полный граф у которого 6 вершин

Об­ра­зо­ва­тель­ный пор­тал для под­го­тов­ки к олим­пи­а­дам
Математика
математика
сайты — меню — вход — но­во­сти
Об олим­пи­а­дах
Ка­та­лог за­да­ний
Ска­зать спа­си­бо
Во­прос — ответ
Добавили олимпиады 2023 года
20 сен­тяб­ря

Рас­ста­ви­ли ат­ри­бу­ты ко всем за­да­ни­ям из олим­пи­ад по ма­те­ма­ти­ке, фи­зи­ке и рус­ско­му язы­ку

1 сен­тяб­ря
До­ба­ви­ли олим­пи­а­ды 2022 года
Внед­ри­ли тёмную тему!
Задания

Тип 21 № 6554

Классификатор: Олим­пи­ад­ная гео­мет­рия. Графы

По­строй­те граф, удо­вле­тво­ря­ю­щий сле­ду­ю­щим усло­ви­ям:

1) Из каж­дой вер­ши­ны вы­хо­дит ровно 4 ребра

2) В графе нет четырёх вер­шин, каж­дые две из ко­то­рых были бы со­еди­не­ны между собой

3) Граф нель­зя по­кра­сить в три цвета «пра­виль­но», то есть так, чтобы любые две вер­ши­ны од­но­го цвета были не со­еди­не­ны.

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

При по­крас­ке та­ко­го графа в три цвета какие-то три вер­ши­ны обя­за­тель­но ока­жут­ся од­но­го цвета. Цикл на семи вер­ши­нах не со­дер­жит тре­уголь­ни­ков, зна­чит, в этом цикле какие-то две из этих трёх вер­шин не будут со­еди­не­ны. Сле­до­ва­тель­но, они будут со­еди­не­ны в до­пол­ня­ю­щем графе, а зна­чит, ни­ка­кая рас­крас­ка не яв­ля­ет­ся «пра­виль­ной».

При­мер ми­ни­маль­ный, по­то­му что граф на 5 вер­ши­нах, ко­то­рые все имеют сте­пень 4, это пол­ный граф и он не удо­вле­тво­ря­ет усло­вию 2).

Граф на 6 вер­ши­нах, ко­то­рые имеют сте­пень 4, един­стве­нен. Для каж­дой вер­ши­ны есть ровно одна, с ко­то­рой та не со­еди­не­на. Каж­дую пару таких вер­шин мы кра­сим в один цвет, и по­лу­ча­ем пра­виль­ную рас­крас­ку в три цвета, сле­до­ва­тель­но, этот граф не удо­вле­тво­ря­ет усло­вию 3.

Критерии проверки:

Три балла ста­вит­ся за при­мер, ещё один балл за до­ка­за­тель­ство того, что граф удо­вле­тво­ря­ет вто­ро­му и тре­тье­му усло­ви­ям

Ещё 2 балла Вы по­лу­чи­те, если Ваш при­мер ми­ни­маль­ный по ко­ли­че­ству вер­шин и Вы это до­ка­же­те.