ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Aлгорітми на графах
         

     

    Інформатика, програмування


    Елементи теорії графів.
    Граф - сукупність точок і ліній, в якій кожна лінія з'єднує дваточки. Точки називаються вершинами, або вузлами, графа, лінії - ребрамиграфа. Якщо ребро з'єднають дві вершини, то говорять, що воно їм інцідентно;вершини, з'єднані ребром називаються суміжними. Дві вершини, з'єднаніребром, можуть збігатися; таке ребро називається петлею. Число ребер,інцідентних вершині, називається ступенем вершини. Якщо два ребраінцідентни одній і тій же парі вершин, вони називаються кратними; граф,що містить кратні ребра, називається мультіграфом.
    Ребро, що з'єднує дві вершини, може мати направлення від однієї вершинидо іншої; в цьому випадку воно називається спрямованим, або орієнтованим,і зображується стрілкою. Граф, у якому всі ребра орієнтовані,називається орієнтованим графом (Орграф); ребра Орграф часто називаютьдугами. Дуги іменуються кратними, якщо вони не тільки мають спільні вершини, але й збігаються за напрямком. Іноді потрібно розглядати не весь граф, айого частина (частина вершин і частина ребер). Частина вершин і всі інцідентние їмребра називаються подграфом; всі вершини і частина інцідентних їм реберназиваються суграфом. Циклом називається замкнута ланцюг вершин. Деревомназивається граф без циклів. Остовне деревом називається пов'язаний суграфграфа, що не має циклів.

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

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

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

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

    Завдання полягає в тому, знайти шлях з вершини A в вершину B. Будемозадавати граф матрицею суміжності, тобто квадратною таблицею NxN, вякої на перетині i-го рядка і j-го стовпця значення TRUE, якщо i та jз'єднані ребром, і FALSE в іншому випадку.

    Пошук в ширину.

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

    Для реалізації алгоритму знадобляться: матриця m [1 .. n, 1 .. n] - матриця суміжності графа; допоміжний масив queue [1 .. n], в якому формуватиметьсячергу, тобто тип даних перший увійшов - першим вийшов (FIFO). Розмір йогодостатній, тому що ми не відвідуємо вершини двічі. З масивом queueпов'язані дві змінні - head і tail. У змінної head буде знаходитисяномер поточної вершини, з якої йде хвиля, а за допомогою змінноїtail нові вершини поміщаються в "хвіст" черги queue; допоміжний масив visited [1 .. n], який потрібен для того, щобвідзначати вже пройдені вершини (visited [i] = TRUE вершина i пройдена); допоміжний масив prev [1 .. n] для зберігання пройдених вершин. Уцьому масиві і буде сформований шуканий шлях; мінлива f, яка прийме значення TRUE, коли шлях буде знайдений.

    Крім того, ми введемо декілька допоміжних змінних, якізнадобляться при організації циклів.

    Program breadth_first_search;

    Const n = 9; m: array [1 .. n, 1 .. n] of boolean =

    (

    (False, True, True, False, False, False, False, False,
    False),

    (True, False, True, False, False, False, True, True,
    False),

    (True, True, False, True, True, False, False, False,
    False),

    (False, False, True, False, True, False, False, False,
    False),

    (False, False, True, True, False, True, False, True,
    False),

    (False, False, False, False, True, False, True, True, True
    ),

    (False, True, False, False, False, True, False, True, True
    ),

    (False, True, False, False, True, True, True, False,
    False),

    (False, False, False, False, False, True, True, False, False)

    );

    Var A, B: integer;

    Procedure A_to_B (A, B: integer);

    Var

    Visited: array [1 .. n] of boolean;

    Prev: array [1 .. n] of integer; c: array [1 .. n] of integer; head, tail: integer; f: boolean; i, v, k: integer; < p> Begin head: = 1; tail: = 1; f: = False;

    For i: = 1 to n do

    Begin

    Visited [ i]: = False;

    Prev [i]: = 0

    End;

    C [tail]: = A;

    Visited [A]: = True;

    While (head

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status