Федеральне агентство з освіти РФ
Державне освітня установа вищої професійної освіти В«Санкт-Петербурзький Державний інженерно-економічний університетВ»
Філія в м. Чебоксари
Факультет фінансів та бухгалтерського обліку
Кафедри фінансів та банківської справи
Реферат
по дисципліни В«МатематикаВ»
На тему: В«орграфа, теорія і застосування В»
Виконала:
Студентка групи 32-08
Рассанова Марія
Науковий керівник:
Качевскій
Дмитро Миколайович
Чебоксари 2009
В
Зміст
Введення
Глава 1. Граф. Загальне уявлення
В· Зв'язність
В· Додаткові визначення
В· Застосування орграфов
Глава 2. Теорія графів
В· Визначення
В· Способи завдання графів
В· Зв'язність
В· Планарність
В· Матричне подання графів
В· Орграфов і соєдініми
В· Орграф і його конденсація
В· Орієнтована подвійність і бесконтурние орграфов
В· Слабкий функціональний орграф
Висновок
Список досліджуваної літератури
В
ВСТУП
Актуальність теми. Теорія графів надає ефективні засоби формалізації задач із всіляких областей: економіки, фізики, хімії, планово-виробничої практики, управління виробництвом, мережевого і календарного планування, інформаційних систем, і багатьох інших. Одним з таких засобів є орієнтований граф. Існує велика кількість завдань, що вирішуються на орграфа. Найчастіше розглядаються завдання про досяжності (тобто про існування шляху, що пов'язує дві задані вершини), про знаходження шляхів, що володіють будь екстремальної характеристикою (наприклад, найкоротший, або найбільш надійний шлях), про випадкових блуканнях, потокова задача. Всі вони добре вивчені і розроблені ефективні алгоритми їх вирішення. При цьому передбачається, що всі шляхи на графі є допустимими, тобто не накладаються ніяких обмежень на досяжність. p> Найбільш відомі роботи в цій області належать Крістофідесу Н., Басакеру Р.Д., Харарі Ф., Берже К., Дейкстра Е., Флойду Р., Замбіцкому Д.К., Оре О., Сааті Т., Фалкерсоном Д.Р., Форду Л.Р.
На відміну від класичного підходу, Басангової Є.О. і ЄРУСАЛИМСЬКИЙ Я.М. було введено поняття орієнтованих графів з нестандартною досяжністю, тобто орграфов, в яких на допустимі шляху накладаються які-небудь обмеження. У звичайному орієнтованому графі, для того щоб одна вершина була досяжна з іншої, необхідне існування шляху, що зв'язує дві ці вершини. У разі ж орграфов з нестандартною досяжністю потрібно, крім того, щоб цей шлях задовольняв деякому умові (обмеження). Зрозуміло, що в цьому випадку класичні алгоритми розв'язання задач на графах безпосередньо незастосовні.
У роботах Єрусалимського Я.М., Басангової Є.О., Логвінова С.Ю., Скороходова В.А., Петросяна А.Г. описані різні види обмежень на досяжність. Так, ЄРУСАЛИМСЬКИЙ Я.М. і Басангової Є.О. розглянуто кілька видів досяжності на частково-орієнтованих графах, на яких присутні орієнтовані та неорієнтовані ребра. Введено поняття змішаної ланцюга, на дуги і ланки якої накладаються різні умови, в залежності від виду обмежень. Наприклад, розглянуті випадки, коли в змішаній ланцюга два неорієнтованих ребра не можуть слідувати безпосередньо один за одним, або дуги і ланки суворо чергуються. p> У роботах Скороходова В.А. розглянуті орграфа з накопиченням неубутною магнитности - го рівня. На таких графах допустимим є магнітно-накопичувальний шлях порядку з неубутною магнитностью, тобто такий шлях, що якщо на - му кроці величина накопиченої магнитности не менше й серед виходять дуг є хоча б одна магнітна, то - я дуга шляху повинна бути магнітної. Інший вид досяжності - вентильно-накопичувальна. У цьому випадку безліч дуг графа представляється у вигляді. У допустимому шляху проходження по дузі безлічі робить доступними для проходження дуги множини. Також розглянуті умови накопичення - ісчезанія і зростання-убування магнитности, вентильна досяжність із зростанням-убуванням доступу та енергії на шляху, механічна досяжність.
Петросяном А.Г. визначена бар'єрна досяжність, при якій безліч дуг розбивається на три попарно непересічних підмножини: дуг, що збільшують бар'єрний показник, дуг бар'єрного переходу і нейтральних дуг. З кожним відрізком шляху пов'язана числова характеристика - бар'єрний показник частки. Шлях допускає бар'єрний перехід рівня, якщо до деякого кроку він накопичив величину бар'єрного показника, не меншу. Ще один вид обмежень - біполярна МАГНІТНОМУ. У цьому випадку визначається величина накопичення біполярної магнитности. Шлях вважається допустимим, якщо він задовольняє умові біполярної магнитности рівня.
Загальним підходом до вирішення завдань на орграфа з обмеж...
