Листик №3 Изоморфизм графов. Плоские графы. Теоремы Фари. Теорема Эйлера



жүктеу 27.51 Kb.
Дата07.02.2019
өлшемі27.51 Kb.

Листик № 3 Изоморфизм графов. Плоские графы. Теоремы Фари. Теорема Эйлера.

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



  1. Докажите, что существует граф с 2n вершинами, степени которых равны 1,1,2,2,...n,n.

  2. Верно ли, что два графа изоморфны, если

1). У них по 10 вершин, степень каждой из которых равна 9?

2). У них по 8 вершин, степень каждой из которых равна 3?



3). Они связны, без циклов и содержат по 6 ребер?

  1. В связном графе степени четырех вершин равны 3, а степени остальных вершин равны 4. Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.

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

  1. Существует ли граф не более чем с 4 вершинами не являющийся плоским.

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

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

  2. (Т.Фари) Любой плоский граф можно правильно нарисовать так, что все ребра графа будут прямолинейными отрезками.

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

  4. (Т. Эйлера) Пусть В, Р - число вершин и ребер графа, Ч - число частей на которые он разбивает плоскость (включая бесконечную часть). Тогда для правильно нарисованного связного плоского графа имеет место равенство: В - Р + Ч = 2.

  5. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?

  6. В выпуклом n-угольнике отметили k точек и соединили их непересекающимися отрезками друг с другом и с вершинами n-угольника так, что n-угольник разбился на треугольники. Сколько получилось треугольников?

  7. Докажите, что для плоского графа справедливо неравенство (если В > 2).

  8. На участке 3 дома и 3 колодца. От каждого дома к каждому колодцу ведет тропинка. Когда владельцы домов поссорились, они задумали проложить дороги от каждого дома к каждому колодцу так, чтобы не встречаться не пути к колодцам. Докажите, что их намерения никогда не смогут осуществиться. (строить мосты или рыть подземный ход нельзя).

  9. Докажите, что полный граф с 5 вершинами не является плоским.

  10. Докажите, что для плоского графа справедливо неравенство Р 3В – 6 (если В > 2).

  11. Можно ли плоский граф, имеющий 10 вершин, степень каждой из которых равна 5, правильно нарисовать?

  12. Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.

  1. Каждое ребро полного графа с 11 вершинами покрашено в черный или белый цвет. Докажите, что либо "белый", либо "черный" граф не является плоским.

  2. Докажите, для любого выпуклого многогранника верна формула: В - Р + Г = 2, где В, Р - число вершин и ребер многогранника, Ч - число его граней.

  3. Пусть Гk - число k -угольных граней произвольного многогранника, Bk - число его вершин, в которых сходится k ребер. Докажите, что 2Р=3B3 + 4B4 +...+ = 3Г3 + 4Г4 +...

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

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

  6. Существует ли выпуклый многогранник, все грани которого являются шестиугольниками?

  7. Докажите, что у любого многогранника найдутся две грани с одинаковым числом сторон. Переведите данное утверждение на язык графов.


Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет