Главная
страница 1
скачать файл

(Комбинаторика, 9.11.03) Семинар 10.

Пусть V –множество вершин графа G(V, X), XVV – множество ребер графа G(V, X). Если | V |=n– конечное число, то граф называется конечным, а n– его порядком. Число | X| называется размерностью графа G(V, X).



Степенью вершины vV называется число

deg v=| { bV : (v, b) X}|.

Графы G(V, X) и H(U,Y) называются изоморфными, если существует такое взаимно однозначное отображение : V U, что (u, v) X тогда и только тогда, когда ((u), (v)) Y. Отображение – изоморфизм. Автоморфизм графа G– это его изоморфизм на себя. Автоморфизмы графа образуют группу.

Граф G называется планарным, если его вершины и ребра можно уложить в плоскости так, что пересекаются. Хроматическим числом (G) графа G называется такое наименьшее положительное число n, что существует отображение множества V на множество {1, 2,…,n} «цветов», при котором смежные вершины получают разные «цвета».


Дерево– это связный граф без циклов.

Задачи


0. Доказать, что для произвольного графа G(V, X) справедливо равенство

.

1. Обозначим через ni(G) число вершин степени i в графе G. Построить все попарно неизоморфные графы без петель и кратных ребер, у которых



  1. n2(G)=1, n3(G)=n4(G)=2 и ni(G)=0 при i2, 3, 4;

  2. n2(G)=3, n3(G)=2, n4(G)=1 и ni(G)=0 при i2, 3, 4;

Указание: а) такой граф один, у него 5 вершин и 8 ребер; б) таких графов 3.

2. Сколько существует попарно неизоморфных 6-вершинных графов без петель и кратных ребер со следующим набором степеней вершин: (2,2, 3, 3, 3,5). Ответ: 2.

3. Изобразить все попарно неизоморфные деревья: а) с 6 ребрами и 3 висячими вершинами; б) с 6 ребрами и 4 висячими вершинами; (деревьев 4) в) с 8 ребрами и 3 вершинами степени 3 (деревьев 3).

4. Указать число компонент связности леса, который имеет 76 вершин и 53 ребра. Ответ: 23.

5. Найти хроматическое число n-вершинного дерева (n>1). Ответ: 2.

6. Доказать, что во всяком дереве содержится с n2 вершинами содержится не менее двух висячих вершин.

7. Подсчитать число попарно неизоморфных 7-вершинных деревьев, удовлетворяющих условию: . Ответ: 6.

8. Найти группу автоморфизмов графа.


9. Определить хроматическое число полного n-вершинного графа. Ответ: n.

10. Какова группа автоморфизмов полного графа с n вершинами. Ответ: симметрическая степени n.

11. Найти все графы с числом вершин меньше или равным 6 такие, что их группа автоморфизмов тождественна. Ответ: 6-вершинных – 8 .

12. Найти группу автоморфизмов графа, состоящего из двух компонент связности, одна из которых есть полный граф степени n, а другая – степени m (nm). Ответ: Sn Sm.

13. Графом n-перестановок назовем граф, вершины которого– все перестановки элементов n-множества, и две вершины смежны в том и только том случае, когда одна из них преобразуется с в другую транспозицией двух элементов. Указать порядок, размерность и степень каждой вершины графа n-перестановок. Является ли граф регулярным?

14. Изобразить на плоскости граф 3-перестановки.

15. Доказать, что граф n-перестановок (n3):


  1. непланарный;

  2. бихроматический;

16. Булевым кубом размерности m называется граф, вершинами которого являются m-мерные вектора из нулей и единиц, причем два таких вектора смежны тогда и только тогда, когда они отличаются одной компонентой. Граф Qm – булев куб размерности m. Доказать, что этот граф: а) связный; б) бихроматический; в) при m>1 гамильтонов.

17. Доказать, что для всякого n3 существует n-вершинный связный граф без петель и кратных ребер, содержащий n–1 вершин с неравными друг другу степенями.

Указание: Набор степеней вершин у одного из таких n-вершинных графов имеет вид {1, 2,…, n–1, [n/2]}.

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

19. Показать, что граф с n вершинами и числом ребер больше (n–1)(n–2)/2 связен.

20. Показать, что число разбиений целого N на n частей так, что наибольшая равна m, равно числу разбиений N на m частей так, что наибольшая равна n.



Указание: Граф Феррера устанавливает взаимно однозначное соответствие между такими разбиениями.
скачать файл



Смотрите также:
Комбинаторика, 11. 03 Семинар 10
31.88kb.
Семинар работает по понедельникам с 15: 30 Порядок работы семинара
31.76kb.
Программа дисциплины Научно-исследовательский семинар «Комбинаторика инвариантов Васильева»  для направления 010100. 62 «Математика»
73.37kb.
Рабочая программа 2 вида Курс по выбору «Комбинаторика»
109.58kb.
Семинар будет проходить в Санкт-Петербургском государственном электротехническом университете
64.49kb.
Семинар Игоря Березина «Аудит эффективности маркетинга с позиции руководителя компании» в Самаре
29.51kb.
Семинар с Бетти Элис Эриксон
2970.43kb.
Программа дисциплины Научно-исследовательский семинар
288.73kb.
Программа дисциплины «Научно-исследовательский семинар \"Политика как призвание и профессия\"»
216.72kb.
Комбинаторика как средство развития логического мышления
715.88kb.
Семинар Практические аспекты формирования городских агломераций, кластеров и индустриальных парков
12.6kb.
Семинар «Геохимия живого вещества»
168.89kb.