Застосування елементів теорії графів для рішення задачі розміщення пунктів обслуговування

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

Для того, щоб формулювати і розв'язувати задачі про розміщення, необхідно ввести нові поняття теорії графів:

  1. центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої від неї вершини є мінімальною.
  2. головним центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої точки на ребрах графа є мінімальною.
  3. абсолютним центром графа називається будь-яка точка на ребрі, відстань від якої до найвіддаленішої вершини графа є мінімальною.
  4. головним абсолютним центром графа називається будь-яка точка, відстань від якої до найвіддаленішої точки є мінімальною.
  5. медіаною графа називається точка, в якій сума відстаней до усіх вершин графа є мінімальною (аналогічно центрам можна ввести поняття головної, абсолютної і головної абсолютної медіани).

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

Читати повністю

Рішення квадратного рівняння за допомогою теореми Вієта

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

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

Тепер сформулюємо основну теорему, для якої, власне, і вводилося поняття зведеного квадратного рівняння: нехай для рівняння коренями являються числа  і (допускається і випадок коли ). Тоді, слідуючи з теореми, справедливими являються настуні формули (формули Вієта):

Читати повністю

Властивості та сума членів геометричної прогресії

Як і у випадку з арифметичною прогресією, при розгляді задач пов'язаних з геометричною прогресією основними являються два питання. Перше з них полягає у знаходженні будь-якого члена прогресії . І друге — у знаходженні суму  членів прогресії. Виходячи з того, що відповідь на перше питання відома (обчислюється за формулою ), то, в даному параграфі, зосередимо свою увагу на виводі формули обчислення суми, але для початку, розглянемо та доведемо деякі властивості геометричної прогресії.

  1. Кожен член знакододатної геометричній прогресії представляє собою середнє геометричне його сусідніх членів (виняток представляє перший член, а у скінченній прогресії також і останній (мають тільки по одному сусідньому члену)).

    Доведемо істенність даного твердження. Отже, для члена , члени і будуть сусідніми. За означенням прогресії маємо: . Звідси, . Перемножимо ці рівності і візьмемо корінь квадратний з отриманого результату. В результаті будемо мати , що і треба було довести.

  2. У скінченній геометричній прогресії добуток членів, рівновіддалених від її кінців, рівні між собою і дорівнюють добутку крайніх членів.

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

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

Читати повністю

Означення та формула обчислення загального члена геометричної прогресії

Геометричною прогресією називається така послідовність чисел, у якій кожен член, починаючи з другого, дорівнює попередньому, помноженому на одне і те саме, задане для даної послідовності, число , яке називається знаменником геометричної прогресії (передбачається, що ).

Якщо число членів прогресії скінченне, то вона називається скінченною геометричною прогресією. В іншому випадку вона називається нескінченною. Наведемо приклади нескінченних геометричних прогресій:

  1.  — знакододатна, монотонно зростаюча геометрична прогресія.
  2.  — знакозмінна геометрична прогресія ( являється меншим нуля).

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

Читати повністю

Властивості та сума членів арифметичної прогресії

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

  1. Кожен член арифметичної прогресії дорівнює середньому арифметичному його сусідніх членів (виняток становить перший член, а у скінченній прогресії також і останній (мають тільки по одному сусідньому члену)).

    Покажемо істенність даного твердження. Отже, для члена , члени та будуть сусідніми. За означенням прогресії можемо записати наступне: . Звідси, . Взявши півсуму останніх рівностей, отримаємо , що і треба було довести.

  2. У скінченній арифметичній прогресії суми членів, рівновіддалених від її кінців, рівні між собою і дорівнюють сумі крайніх членів.

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

    Звідси, виходячи з того, що , отримаємо , що і треба було довести.

Виведемо тепер формулу для суми членів скінченної арифметичної прогресії. Для прогресії, що має  членів, позначимо цю суму через . Запишемо вираз суми  двічі, один раз розташувавши члени прогресії по зростанню їх номерів, і другий раз — по спаданню:

Читати повністю

Послідовна розмальовка графа в середовищі програмування delphi

В параграфі розглядається програма, основним призначенням якої є відшукання хроматичного числа та здійснення правильної розмальовки вершин неорієнтованого графа, написана в середовищі Delphi 7. Зазначимо, що внизу сторінки міститься посилання, скориставшись якими можна завантажити delphi-проект, а в цій статті коротко опишемо елементи його головної форми.

Головне вікно проекту "Послідовна розмальовка графа"

Отже, головна форма delphi-програми ділиться на три частини і складається з панелі інструментів (компонент типу TPanel), графічного редактора (компонент типу TImage) та області виводу резільтатів (компонент типу TMemo):

Читати повністю

Означення та формула обчислення загального члена арифметичної прогресії

Арифметичною прогресією називається така послідовність чисел, кожен член якої (починаючи з другого) дорівнює сумі попереднього члена і деякого фіксованого числа , яке називається різницею або кроком арифметичної прогресії.

До прикладу натуральний ряд чисел є нескінченною арифметичною прогресією з різницею , а послідовність непарних і парних чисел — нескінченними арифметичними прогресіями, для кожної з яких різниця дорівнює числу два ().

Арифметична прогресія при являється монотонною послідовністю: якщо , то прогресія зростає, якщо , то прогресія спадає, при вона постійна. Нескінченні арифметичні прогресії, для яких різниця не дорівнює нулю, як необмежені послідовності, границі не мають. Вони відносяться до категорії розбіжних послідовностей.

Читати повністю

« Попередня сторінкаНаступна сторінка »