Звязність орієнтовного графа. Маршрут, цикл, ланцюг.

Date: 2014-03-11; view: 537.

Звязність неорієнтованого графа. Маршрут,шлях,цикл,ланцюг.

План

Та інші компоненти зв'язності.

Сформувати вміння визначати маршрути, цикли,ланцюги

Маршрути, шляхи, ланцюги, цикли.

Тема: Зв’язність орієнтованого і неорієнтованого графа.

Вопрос 9. Анализ деловой активности

Деловая активность предприятия оценивается целой системой показателей, отражающих марксовскую схему Д – Т ... П ... Т - Д´.

Чем быстрее проходит оборот в этой схеме, тем выше деловая активность.

Взаимосвязь между вложенным капиталом и результатом можно представить в виде схем: выручка от реали-

Прибыль прибыль зации продукции

——————— = ———————— * ———————— ,

среднегодовая выручка от реали- среднегодовая

сумма капитала зации продукции сумма капитала

то есть ЭР = R * Коб,

где ЭР – доходность инвестирования в производство капитала,

R – рентабельность продаж,

Коб – коэффициент оборачиваемости капитала.

Показатель, отражающий время одного оборота (Поб):

Д среднегодовая сумма капитала

Поб = —— = ————————————— * Кол-во календарных дней

Коб выручка от реализации в периоде (360, 90, 30 дней)

Экономический эффект в результате ускорения оборачиваемости капитала выражается в относительном высвобождении средств из оборота, увеличении суммы прибыли и частей её распределения.

Поскольку сумму прибыли можно представить как

П = Rпродаж * Коб * ∑ К, то прирост прибыли за счёт включённых в модель факторов рассчитывается методом абсолютных разниц.

∆П(Коб) = ∆Коб * Rпродаж * ∑К1

Мета: ознайомити з поняттям зв'язності неографа та орграфа,

1.Нехай G - неорієнтований граф

Означення:

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

Початок шляху – це вершина інцидентна ребру і не інцидентна ребру .

Кінець шляху – це вершина інцидентна ребру і не інцидент на .

Якщо ребра – кратні – потрібно додатково вказувати ,яку із двох інцидентних вершин вважати початковим(кінцевим) маршрутам.

Шлях довжини к – це послідовність ,що містить к ребер.

Іншими словами , довжина шляху – це кількість ребер у ньому; при цьому кожне ребро враховується стільки разів, скільки воно зустрічається в шляху.

Будемо позначати шлях як .

Маршрут (шлях), всі ребра якого різні називається ланцюгом.

Ланцюг,що не перетинає себе, тобто не моє вершин,що повторюються називається простим.

Приклад.1. Визначаємо можливі маршрути(шляхи) і їхню довжину з вершини в у графі що зображеному на (мал.1)

(мал.1)

Розв’язання:

з вершини у ведуть, наприклад, шляхи:

1) ‑ довжини 2; 5) ‑ довжини 6;

2) ‑ довжини 4; 6) ‑ довжини 6;

3) ‑ довжини 4; 7) ‑ довжини 8;

4) ‑ довжини 6; 8) ‑ довжини 10.

Шляхи: 6), 8) не є простими.

Шляхом 5,8 не є простими

Шлях є простим, якщо він не містить ребер, які повторюються.

Означення:

Шлях, в якому збігається початок і кінець називається циклічним.

Циклічний маршрут називається,циклом якщо він є ланцюг, і простимциклом – якщо це простий ланцюг.

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

Означення:

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

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

Приклад.2. Граф, зображений на (мал.2) – не зв'язний, а граф на (мал.3) – зв'язний.

(мал.2) (мал.3)