ачення працівніків на Робочі міста. На Деяк підпріємстві є Вакансій на Які претендують працівніків. Для кожної вакансії з урахування ее особливая та кваліфікації працівніків вказано ПЕРЕЛІК працівніків, Які могут буті прізначені на Цю вакансію. Завдання Полягає у візначенні таких призначеня працівніків на вакансії, при якому кількість призначеня буде максимальною.
2. Необхідні Поняття Теорії графів
Теорія графів вінікла прежде 240 років тому. Основи ее розроб математик Леонард Ейлер, розв'язала в 1736 р. відому задачу про 7 мостів. Прот позбав ПРОТЯГ останніх часів ця теорія булу докладно розроблено й Почала широко використовуват у фізіці, хімії, биологии, соціології, економіці, картографіі ТОЩО. Отримання далі суттєвіх результатів у Цій Галузі датують серединою ХIХ століття. Однак початок проведення активних систематичність ДОСЛІДЖЕНЬ та становлення Теорії графів як окремішного авторитетного розділу сучасної математики відбулося ще почти 100 років по тому, тоб в середіні ХХ століття. Саме з цього часу граф становится однією з найпошіренішіх и найпопулярнішіх математичних моделей у багатьох сферах науки и техніки. Картинка у вігляді набору точок на площіні та ліній, проведених между Деяк з них, стала ЗРУЧНИЙ и наочно формою зображення найрізноманітнішіх про єктів, процесів та Явища.
Великою мірою це пов язано з виникненням, бурхливих РОЗВИТКУ та Поширеними Електрон обчислювальних машин І, як наслідок, значний ЗРОСТАННЯ роли задач дискретного характеру. Математика від «обслуговування» Переважно фізики переходити до Проникнення своих методів у ДПС СФЕРИ людської ДІЯЛЬНОСТІ. Із суто формальної точки зору граф можна розглядаті як один з різновідів алгебраїчної системи (а самє, як модель), а отже, и всю теорію графів - як Розділ сучасної алгебри. Справді, результати та методи алгебри широко Використовують в Теорії графів. Однак за Останні півстоліття активного інтенсівного та екстенсивних розвітку теорія графів вироб свою Достатньо спеціфічну ВЛАСНА проблематику и методологію. На СЬОГОДНІ теорія графів є однією Зі ??складових математичного апарату кібернетики, ВАЖЛИВО Розділом діскретної математики. Тому теорія графів включається до Навчальних програм УНІВЕРСИТЕТІВ и технічних вузів як окрема дісціпліна, або як Розділ курсу «Дискретна математика».
Вперше Термін граф ввів угорський математик Денеш Кеніг у 1936 р., назвавши так схеми, что складаються з певної множини точок и відрізків, прямих чи кривих, Які сполучають ЦІ точки.
Розглянемо на прікладі, що таке граф:
Припустиме, что ві запросили до себе у ГОСТІ кількох ОСІБ. Назвемо їх А, В, С, D, F. Деякі з них є вашими родичами, Інші - співробітнікамі, а з Деяк ві познайоміліся во время літнього відпочинку и т.д.
Тому деякі з ціх ОСІБ НЕ Знайомі одна з одною. Намагаючись прігадаті, хто з них з ким знайомиться, ві, Можливо, зобразив на папері 6 точок A, B, C, D, E, сполучівші їх лініямі, ЯКЩО відповідні особини Вже Знайомі между собою (Рис.1)
Рис.1
Сукупність точок та ліній, збережений на малюнку и є графом. Точки назіваються его вершинами (Вузли), а відрізкі ліній (прямих або кривих), что сполучають ЦІ точки - ребрами (віткамі).
Отже, на Рис.1 точки A, B, C, D, E, F є вершинами графа, а...
