На головну

ВПРАВИ

  1. Ваші дії по наданню першої допомоги при травмах під час занять фізіческіміупражненіямі. Накладіть пов'язку на голову або гомілковостопний суглоб
  2. Діагностика і самодіагностика організму при заняттях фізичними вправами і спортом.
  3. Діагностика і самодіагностика стану організму при регулярних заняттях фізичними вправами і спортом.
  4. Динамічні підготовчі вправи
  5. ЗАВДАННЯ І ВПРАВИ
  6. Загартовування в поєднанні з фізичними вправами
  7. Коливання частоти серцевих скорочень при різних фізичних вправах у дітей

1. Доведіть теореми 65.1 і 65.2.

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

3. Доведіть, що пара векторів (З2, 2) і (3, 22, 1) є графічною, і побудуйте її реалізацію.

4. Побудуйте орієнтований граф, для якого вектор (33, 22) Є як списком полустепені результату вершин, так і списком полустепені заходу вершин.

5. Доведіть, що такі властивості орграфа G еквівалентні:

1) G - Бесконтурний граф;

2) граф G і його конденсація G * ізоморфні;

3) кожен маршрут орграфа G є шляхом;

4) вершини орграфа G можна впорядкувати так, що його матриця суміжності буде верхньою трикутною матрицею.

6. полустепені результату вершини турніру називається кількістю очок вершини. Доведіть, що в будь-якому турнірі відстань від вершини з максимальною кількістю очок до будь-якої іншої вершини дорівнює 1 або 2.

7. Доведіть, що в транзитивному турнірі існує рівно одінгамільтонов шлях.

8. Доведіть, що ребра будь-якого неориентированного графа можна так орієнтувати, що в отриманому орграфе | d+(V) - d-(V)| <= 1 для будь-якої вершини v.

9. Покажіть, що будь-який турнір або є сильним, або може бути перетворений в сильний зміною орієнтації тільки однієї дуги.

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

11. Транзитивним замиканням орграфа G називається орграф G ', для котрого VG '= VG, а (І, v) G ' тоді і тільки тоді, коли в орграфе G вершина v досяжна з і. Транзитивная редукція орграфа G визначається як орграф з найменшим числом дуг, транзитивне замикання якого збігається з транзитивним замиканням орграфа G. Покажіть, що якщо орграф не має контурів, то його транзитивній редукція єдина.

12. Нехай G - Орграф без петель з п вершинами і m дугами. Доведіть, що якщо G є зв'язковим, але не сильним Орграф, то п - 1 <= m <= (п - 1)2, а якщо G - Сильний орграф, то п <= m <= п <= (п - 1).

13. Доведіть, що в орграфе порядку п, для будь-яких двох несуміжних вершин и и v якого вірно нерівність d (u) + d (v)> =2п - 3, Існує гамільтонів шлях.

14. Орграф L (G), вершини якого відповідають дугам орграфа G и (І, v) AL (G) тоді і тільки тоді, коли відповідні дуги породжують в G маршрут, називається ребровим Орграф. Висловіть число вершин і число дуг реберного орграфа L (G) через аналогічні параметри орграфа G.

15. Цілочисельна функція g (v)> = 0, v VG, називається функцією Гранді орграфа G, якщо для будь-якої вершини v значення g (v) збігається з мінімальним з тих невід'ємних цілих чисел, які не належать безлічі {G (u): і Г (у)}. Покажіть, що якщо кожен підграф орграфа G володіє ядром, то існує функція Гранді орграфа G.



База і ядро | Основні визначення і властивості

Основні визначення | Полустепені результату і полустепені заходу | незалежні безлічі | розмальовки | реалізації гіперграфу | попередні відомості | Пошук в глибину | Відшукання двусвязного компонент | мінімальний остов | найкоротші шляхи |

© um.co.ua - учбові матеріали та реферати