Тема Основні властивості графів icon

Тема Основні властивості графів



НазваниеТема Основні властивості графів
Дата конвертации20.05.2013
Размер16.2 Kb.
ТипДокументы
скачать >>>

Заняття G 1.


Тема Основні властивості графів.

Мета Засвоєння понять, пов'язаних з маршрутами та циклами, одержання навичок аналізу властивостей графів.

Теоретичні питання: Маршрут, ланцюг, цикл, зв'язність вершин та графу вцілому, степінь вершини.

Приклади:

  1. Підрахувати cкільки ребер в повному графі (орграфі) з вершинами?

  2. Навести приклад графа, в якому існує простий ланцюг з вершини v1 в вершину v2 та з вершини v2 в вершину v3, але не існує простого ланцюга з v1 в v3 через v2.

  3. Довести, що зв'язний граф з вершинами має не меньше ніж ребро. (Г.4-1.7)

  4. Довести, що у зв'язному графі з n вершинами між довільними двома вершинами існує маршрут довжини не більше ніж n-1.

  5. Довести, що коли у графі G рівно дві вершини v та w мають непарні степені, тоді ці вершини є зв`язними у графі G.

  6. Довести, що будь-який замкнений маршрут непарної довжини містить в собі простий цикл. Чи вірно це для маршрутів парної довжини. (Г.4-1.6)

  7. Довести, що якщо зі зв'язного графа видалити довільне ребро, що міститься у деякому простому циклі, то граф залишиться зв'язним. Чи вірно це для циклу, замкненого маршруту? (Г.4-1.11)


Домашне завдання:

  1. Довести, що кількість вершин непарної степені графа парна.

  2. Довести, що у будь-якому графі з не меньш ніж 2 вершинами знайдуться дві вершини однакового ступеня. (Г.4-1.3)

  3. Довести, якщо у графі з n вершинами (n2) тільки одна пара має однакову степінь, то у цьому графі завжди існує: або одна ізольована вершина, або одна вершина яка суміжна з всіма іншими.

  4. Довести, що у графі з вершинами та компонентами зв'язності кількість ребер не перевищує . (Г.4-1.8)

  5. Довести, що у зв'язному графі будь-які два простих ланцюги максимальної довжини мають щонайменьше одну спільну вершину. Чи будуть вони завжди мати спільне ребро? (Г.4-1.10)

  6. Довести, що для довільного графа або він сам, або його доповнення є зв'язним.

  7. Навести приклад графу, який є ізоморфним власному доповненню.

  8. Довести, якщо у графа всі прості цикли мають парну довжину, то він не має жодного цикла непарної довжини.





Похожие:

Тема Основні властивості графів iconТема Властивості графів. Ізоморфізм графів
Мета Засвоєння понять, пов'язаних з обходами графів, одержання навичок порівняння графів на ізоморфізм
Тема Основні властивості графів iconТема Планарні графи, фарбування графів
Мета Зв'язок дерев та планарних графів, застосування теореми Ейлера для планарних графів. Розфарбовування графів, одержання навичок...
Тема Основні властивості графів iconРозкладність графів. Морфізми кульових структур груп І графів
Позначимо через I граф з множиною вершин N={1,2…} І множиною ребер E={(1,2),(2,3),…}. В цьому параграфі охарактеризовано кульові...
Тема Основні властивості графів iconПервісна функція І неозначений інтеграл. Основні властивості неозначеного інтеграла. Таблиця основних інтегралів

Тема Основні властивості графів iconРозкладність графів. Комбінаторні розміри підмножин графів І груп
Теорема 1 Якщо множину вершин V довільно зв'язного графа Gr(V,E) розбито на скінченне число підмножин V=V1 V2 …Vn, то принаймні...
Тема Основні властивості графів iconЛекція №15 Тема: Наслідування. Доступ до членів класу
Використовуючи Наслідування, можна створювати загальні класи, що визначають властивості, характерні для всієї сукупності споріднених...
Тема Основні властивості графів iconЕлементи теорії графів Основні поняття
Графи там, де є елементи (вершини) та зв'язки між ними (ребра). Приклади – географічні схеми, комбінаційні схеми з функціональних...
Тема Основні властивості графів icon8. Елементи теорії графів Основні поняття
Графи там, де є елементи (вершини) та зв'язки між ними (ребра). Приклади – географічні схеми, комбінаційні схеми з функціональних...
Тема Основні властивості графів iconПланы семинарских занятий (очная форма обучения, нормативные сроки) тема 3 тема 4 тема 5 тема 6 тема 7 тема 8 тема 9 тема 10 тема 11 тема 12 тема 13 тема 14 тема 15 тема 16 тема 17 тема 18 тема 19 тема 20 тема 21 тема 22 тема 23 тема 24 тема 25 тема 26
Понятие и соотношение предмета и объекта науки. Предмет теории государства и права
Тема Основні властивості графів iconРозкладність графів. Врівноважені розбиття скінченних графів
Розглянемо скінченний зв'язний граф Gr = (V,E) з множиною вершин V і множиною ребер E. Для довільних двох вершин X,yV позначимо...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы