Реферат Задачі, які приводять до поняття графа (реферат)


СкачатиСкачать (DOC|ZIP):
Задачі, які приводять до поняття графа (реферат)

РЕФЕРАТ

на тему:

Задачі, які приводять

до поняття графа

1. Поняття про графи

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

Граф - це множина точок (вершин), які з”єднані між собою лініями, що називаються дугами або ребрами.

Приведемо приклад задачі, яка може бути розв”язана, за допомогою графів.

Задача 1:

На вечірку запрошено шестеро людей, чи може бути така ситуація,
що кожен знав тільки двох запрошених.

Розв”язання:
Кожного з цієї компанії зобразимо точкою, і пронумеруємо їх. Якщо двоє знайомі, то з”єднаємо їх відрізком (ребром). Виявляється, що така ситуація не тільки можлива, але й може описуватися декількома схемами.

Тобто можна сказати, що граф-це сукупність об”єктів, зв”язками між якими служать ребра.

Приклади графів з декількома вершинами та ребрами.
На малюнку 4 показаний граф з чотирма вершинами та шістьма ребрами
На малюнку 5 зображено граф з п”ятьма вершинами та двома ребрами

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

2. Задача Ейлера – як яскравий приклад задачі,

яка приводить до поняття графа

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

Буваючи в Кенігсберзі, прогулюючи по його набережних, Ейлер звернув увагу на оригінальне розташування семи мостів міста. Причиною цьому був вигадливий течії рукавів Прегеля, з'єднаних протокою, що охоплюють з півночі і півдня острів Кнайпхоф, а потім зливаються разом.

У підручниках зображується схема

розташування мостів.

Приблизно ось така >>>

Витончена по своїй конкретності Задача семи мостів Кенігсберга була сформульована Ейлером у 1759 р. у такий спосіб: "як пройти по семи мостах, не проходячи по одному двічі".

Для рішення цієї задачі Ейлер вводить поняття «мережі» (щоназивається в наш час «графом») як безлічі непересічних ребер чи зв'язків, що з'єднують пари вершин. Ось так виглядає цей граф, якщо

накласти вершини і зв'язки на карту центра нашого міста >>>>>>

Цей же граф для числа "7" у чистому виді без "підкладки". >>>

У кожній мережі Ейлер підраховує зв’язки, що приходять у вершини. Якщо число зв'язків непарне, таку вершину Ейлер називає «неправильною» або «дивною». Вершина з парною кількістю зв'язків – «правильна» (у першоджерелі – «мудра»). Як бачимо, усі вершини в нашій мережі з'єднують 3 чи 5 зв'язків. Отже усі вони - неправильні. Виходить, так званої безупинної «доріжки Ейлера», яка проходить через кожну вершину тільки один раз для цього числа не існує.


СкачатиСкачати:Задачі, які приводять до поняття графа (реферат)


Схожі реферати:
  • Джеймс Джойс - видатний письменник-модерніст (лекція)
  • Основні риси сучасних податкових систем розвинутих країн (реферат)
  • Класифікація підприємств малого бізнесу. Особливості фінансової діяльності ТзОВ (Реферат)
  • Рецепція ринкового спадкового права в сучасному спадковому праві України ПЛАН Вступ Римське спадкове право як джерело сучасног
  • Економічна сутність і функції страхування Страхування виникло й розвивалося як протистояння стихійним лихам і прояву всіляких негараздів, несприятлив
  • Особливості виховного процесу в Україні (курсова робота)
  • Курсова робота: Еволюція грошово-кредитної системи Росії Зміст Вступ 1. Еволюція кредитної системи дореволюційної Росії. 2. Грошово-кредитна система Росії
  • Реферат з релігієзнавства: Християнство та сім’я Вступ . Я вважаю тему сім я та шлюб дуже важливою тому , що сьогодня
  • Поняття пропозиції. Ринкова рівновага
  • КОНТРОЛЬНА РОБОТА з міжнародного аудиту на тему: Розвиток аудиту в Російській Федерації, Казахстані та Білорусі Зміст ј ИГЇ Рo "1-3" ј




  • Скористайтеся пошуком:
    Loading

    Пошук :

    0.032314