Комбинаторика, 11. 03 Семинар 10



Скачать 31.88 Kb.
Дата08.10.2012
Размер31.88 Kb.
ТипСеминар

(Комбинаторика, 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 iconСеминар по алгебре и линейной оптимизации, посвященный 100-летию со дня рождения С. Н. Черникова
Третий Международный семинар “Комбинаторика пространств модулей, кластерные алгебры, узлы и топологические рекурсии”
Комбинаторика, 11. 03 Семинар 10 iconПриложение элементы комбинаторики Комбинаторика
Комбинаторика – это наука о том, сколько различных комбинаций, удовлетворяющих определенным условиям, можно составить на элементах...
Комбинаторика, 11. 03 Семинар 10 iconРекомендации по изучению темы «Комбинаторика» в курсе математики в 9-11 классах
Данная работа предназначена для учителей математики 9-11 классов при изучении темы «Комбинаторика»
Комбинаторика, 11. 03 Семинар 10 iconЛекция 9: Комбинаторика-2
Практически вся эта лекция будет посвящена разнообразным свойствам особых чисел, называемых попросту "цэшками", а по-научному числами...
Комбинаторика, 11. 03 Семинар 10 iconКомбинаторные задачи Рассмотрим задачи математической науки, которая называется комбинаторикой. Комбинаторика
Комбинаторика это раздел математики, отвечающий на вопросы сколькими способами можно выбрать элементы определенного множества, если...
Комбинаторика, 11. 03 Семинар 10 iconСеминар по математике для учеников 8-12-классов будет работать по вторникам с 16. 15. Первое занятие состоится 1 марта. Основная тема комбинаторика. Руководитель семинара А. Я. Каневский
Кружок по спортивному программированию работает по понедельникам в 17. 00. Тематика кружка посвящена методам решения олимпиадных...
Комбинаторика, 11. 03 Семинар 10 iconСеминар для клинических интернов по вопросам социальной педиатрии. Семинар
Семинар подготовила и провела ассистент кафедры детских болезней педиатрического факультета, к м н. В. В. Самохвалова
Комбинаторика, 11. 03 Семинар 10 iconСеминар №1 3 Теория 3 Практика: Основы работы с интерфейсом и администрирование системы. 11 Семинар №2 12 Теория: 12
...
Комбинаторика, 11. 03 Семинар 10 iconСеминар "Основные понятия математики" 1-2 курс Семинар работает по пятницам с 14: 00 Цель этого семинара продемонстрировать участникам, "
Семинар предназначен в основном для студентов первого курса; часть тем (но не все!) будут такие же, как в прошлом году
Комбинаторика, 11. 03 Семинар 10 iconСеминар №1 23 октября семинар №2 30 октября Искусство Древнего Египта 13 ноября семинар №3

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org