Степінь вершини

Вершини в графі можуть відрізнятись тим, скільком ребрам вони належать.

Степінь вершини - це кількість ребер, яким належить дана вершина.

Наприклад, в графі, показаному нижче

Вершина 1 має степінь2

Вершина 4 має степінь3

Вершина 2 має степінь 3

Степінь кожної вершини повного графа на одиницю менша числа його вершин। Вершина називається парною, якщо її степінь - число парне। Вершина називається непарною, якщо її степінь – число непарне.Вершини, які не належать жодному ребру, називаються ізольованими.Дослідимо деякі властивості графа на такій задачі.

Учасники конференції при знайомстві обмінювались конвертами з адресами. Довести, що: а). Всього було передано парну кількість конвертів.б).Число учасників, які обмінювались конвертами непарне число разів – парне.
Доведення:Нехай учасники конференції А1, А2, А3, ... , Аn – вершини графа, а ребра, які їх з”єднують- передані конверти.
а).Так як кожне ребро – це пара конвертів, то кількість переданих конвертів завжди в два рази більша за кількість ребер в графі.б).Кількість конвертів завжди рівна сумі степенів вершин графа, вона парна з попереднього доведення. Сума степенів буде парною тоді, коли вона не містить непарних доданків, або містить їх парну кількість.
В ході рішення задачі було доведено дві теореми.
Теорема 1.
В графі сума степенів його вершин завжди парне число і рівна подвоєному числу ребер графа.
Теорема 2.
Число непарних вершин будь-якого графа парне.
Теорема 3.
В будь-якому графі, який має n вершин( n>=2) завжди знайдеться хоча б дві вершини з однаковим степенем। ДоведенняДоведемо цю теорему від супротивного.Нехай в графі всі вершини мають різні степені, тобто для n вершин ці значення складають від 0 до n-1. Але якщо існує вершина з степенем 0, то вершина з степенем n-1 не може існувати, так як ця вершина повинна бути з”єнаною ребрами з усіма вершинами в тому числі і з тою, що має степінь 0. Інакше кажучи, в графі з n вершинами не можуть бути присутні вершини з степенями 0 та n-1. Отже знайдуться хоча б дві вершини, степені яких рівні між собою.

Завдання

1. Чи знайдеться граф, у якого 5 вершин, і одна вершина ізольована, а друга з степенем 4?

2. В бюро по туризму , яке складає маршрути мандрівок для автотуристів, які повинні проїхати з пункту S в пункт R і продивитися всі місцеві визначні місця. Пункти і всі шосейні дороги, з'єднані між собою представлені на схемі.
Допоможіть бюро скласти такий маршрут, щоб туристи в кожне пункт попадали лише один раз. Випишіть послідовність пунктів для кожного знайденого маршруту.

3. Скільки вийде шматків паперу, якщо спочатку було m шматків, деякі шматки розрізали на 5 частин, а всього було розрізано k шматків.
4. Скільки отримається шматків паперу, якщо спочатку було m шматків, деякі з шматків розрізали на n частин, а всього було розрізано k шматків.