лучшие книги по экономике
Главная страница

Главная

Замовити роботу

Последние поступления

Форум

Создай свою тему

Карта сайта

Обратная связь

Статьи партнёров


Замовити роботу
Книги по
алфавиту

Б
В
Г
Д
Е
Ж
З
И
К
Л
М
Н
О

Дискретний аналіз

Страницы [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]
[ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ] [ 32 ]
[ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] [ 38 ] [ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] [ 48 ] [ 49 ] [ 50 ]

Термінологічний словник

Ациклічний граф (ліс, продерево) — граф, в якому немає циклів.
Відкритий маршрут — незамкнений маршрут.
Відстань d(u, v)між двома вершинами u та v графа G — це довжина найкоротшого простого ланцюга
Гамільтоновий графграф, що містить гамільтоновий цикл.
Гамільтоновий цикл — простий остовний цикл.
Геодезична — найкоротший простий ланцюг, що сполучає дві вершини графа.
Граф — математичне поняття, що визначається двома характе-
ристиками:
1)  деякою непорожньою множиною V, елементи якої зазвичай називаються вершинами(точками, вузлами, сплолученнями,0-симплек­сами або просто елементами);
2)  множиною Х всіх неупорядкованих пар різних вершин із V (відповідностей). Кожну пару х = {u, v} вершин в Х називають ребром (лінією, дугою, гілкою,1-симплексом, елементом) графа.
Дерево — це зв’язний ациклічний граф.
Діаметр графа — довжина найдовшої геодезичної.
Добуток графів G1 ? G2 — граф, у якого дві вершини u = (u1, u2) та
v =
(v1, v2)з V = V1? V2 суміжні тоді, і лише тоді, якщо u1 = v1, а u2 та v2 суміжні або u2 = v2, а u1 та v1 суміжні.
Довжина маршрутудорівнює кількості ребер у ньому (причому кожне ребро рахується стільки разів, скільки воно зустрічається в даному маршруті).
Ейлеровий графце граф, що містить ейлеровий цикл.
Ейлеровий цикл — замкнений ланцюг, який містить усі вершини та всі ребра графа.
З’єднання графів G1 + G2 — сукупність усіх ребер, що мають ці графи (V1 та V2).
Замкнений маршрут — маршрут, який починається і закінчується в одній і тій же вершині, тобто перша й остання вершини його збігаються.
Зв’язний граф — граф, у якому будь-яка пара вершин сполучена простим ланцюгом.
Ізоморфними вважають графи G та H (записується G @ H або інколи G = H), якщо між їх множинами вершин існує взаємно однозначна відповідніcть, що зберігає суміжність.
Інцидентні вершина та ребро — ребро, яке сполучає дану вершину з іншою.
Композиція графів G = G1[G2] має V = V1 ? V2 за множину вершин та вершина u = (u1, u2) суміжна з v = (v1, v2) тоді, і лише тоді, якщо u1 та v1 суміжні або u1 = v1, а u2 та v2 суміжні.
Компонента зв’язності (компонента графа) — максимальний зв’язний підграф графа.
Контурнетривіальний замкнений маршрут, у якому всі вершини різні (за винятком першої та останньої).
Ланцюг (trail) — маршрут, у якому всі ребра різні.
Маршрут— послідовність вершин та ребер, що попарно чергуються.
Матриця інциденцій B=||bij|| — (n ? m)-матриця, в якій bij = 1, якщо vi та xj інцидентні, а в іншому випадку bij = 0.
Матриця суміжностей (часто використовують термін «матриця суміжності») A = ||aij|| поміченого графа G з n вершинами — це квадратна (n ? n) матриця, в якій aij = 1, якщо вершина vi суміжна з vj, а в іншому випадку aij = 0.
Матриця суміжностей поміченого орграфа D з п вершинами — це квадратна матриця А = ||aij||, де aij = 1, якщо дуга vivj належить D, а в іншому випадку aij = 0.
Матриця циклів С = ||cij|| графа G — це матриця, в якій для кожного простого циклу графа G є рядок і для кожного ребра — стовпець, причому, cij = 1, якщо i-й цикл містить ребро, а в іншому випадку xj, cij = 0.
Мережа — скінченний односторонній орієнтований граф, для якого виконуються умови:
а) орграф містить дві, і тільки дві такі вершини, одна з яких не має вхідних дуг, а інша — вихідних. Перша, початкова, вершина такого графа називається джерелом, а друга, кінцева, — стоком;
б) кожній дузі графа зіставляється деяке невід’ємне число, яке називається пропускною здатністю.
Мультиграф — граф без петель, але пари вершин можуть сполучатися кількома ребрами.
Напівмаршрут — це послідовність вершин та дуг, що чергуються: v0, x1, v1,..., xn, vn, але дугою xi може бути як vi–1vi, так і vivi–1.
Напівстепені входу та виходу орграфав вершині — кількість дуг, які відповідно входять та виходять із даної вершини.
Напівшлях, напівконтур — визначаються аналогічно поняттю «напівмаршрут».
Направлений графце граф, який не має симетричних пар орієнтованих ребер.
Незв’язний орграф — слабкий орграф.
Об’єднанняграфів G1 E G2 — це граф, множиною вершин якого є
V = V1 E V2, а множиною ребер — Х = Х1 E Х2.
Однорідний степеня mn орієнтований граф — це орграф, напівсте­пені входу та виходу для всіх вершин якого мають одне і те ж значення mn.
Односторонньо зв’язний (або односторонній) граф — це граф, для будь-яких двох вершин якого хоча б одна досяжна з іншої.
Орієнтований граф, або орграф, D складається зі скінченної непорожньої множини V вершин та заданого набору X впорядкованих пар різних вершин. Елементи Х називаються орієнтованими ребрами, або дугами.
Орієнтований маршрут — це послідовність вершин та дуг орграфа, що чергуються: v0, x1, v1,..., xn, vn, де xi = vi–1 vi.
Остовний маршрут — це маршрут, який містить всі вершини графа.
Петля — ребро, яке сполучає вершину саму з собою.
Підграф — граф, отриманий з іншого графа вилученням вершин та інцидентних з ними ребер.
Повний граф — граф, у якому будь-яка пара вершин сполучена хоча б одним ребром.
Потік — функція, що відображує множину дуг орграфа в множину цілих невід’ємних чисел та задовольняє наступні умови:

  • для кожної дуги ці числа не перевищують її пропускну здатність;
  • для кожної з проміжних вершин сума всіх вхідних потоків дорівнює сумі всіх вихідних потоків.

Простий ланцюг — маршрут, у якому всі вершини (і відповідно ребра) різні.
Простий цикл — замкнений ланцюг, у якому всі n вершин різні і n ? 3.
Псевдограф — мультиграф з петлями.
Розріз графа. Розділимо множину вершин мережі на дві взаємодоповнюючі множини P та`P так, що s I P та t I  Розріз графа складає множина дуг, які сполучають вершини підмножин P та
Сильно зв’язний (або сильний) орграф — це орграф, будь-які дві вершини якого взаємно досяжні.
Симетрична пара орієнтованих ребер — дві дуги, які сполучають одну й ту ж пару вершин, але у протилежному напрямку.
Скінченний граф — граф, який має скінченну кількість вершин.
Слабо зв’язний (або слабкий) граф — граф, будь-які дві вершини якого сполучені напівшляхом.
Степінь вершини неорієнтованого графа — кількість вершин, інцидентних цій вершині.
Степінь графа — максимальна величина степенів вершин.
Суміжні вершини — вершини, які з’єднані ребром.
Суміжні ребра — ребра, які інцидентні одній і тій же вершині.
Теорема Форда—Фалкерсона. У будь-якій мережі величина максимального потоку дорівнює величині мінімальної пропускної здатності розрізу.

Страницы [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]
[ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ] [ 32 ]
[ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] [ 38 ] [ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] [ 48 ] [ 49 ] [ 50 ]


ВНИМАНИЕ! Содержимое сайта предназначено исключительно для ознакомления, без целей коммерческого использования. Все права принадлежат их законным правообладателям. Любое использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием содержимого сайта.
© 2007-2020 BPK Group.