На тази страница ще намерите готови примери за теория на графите (списък с дискретна математика). Графика теория води началото си от 18-ти век, когато Ойлер пише известната си статия за Konigsberskih мостове (вж. Решения на алгоритъма на Ойлер). Сега достигане теория на графите се използват в строителството, програмиране, електротехника, социология, икономика, биохимия, телекомуникации и транспорт планиране, комуникации, психология и т.н.
Какви видове задачи се решават от студенти?
Проблеми решени в рамките на теория графика могат да бъдат разделени в няколко групи:
- Определяне на графика и неговите свойства. Цели за изграждане на графиката от предварително определен брой върхове и ръбове, и изграждането на съседство матрицата на падане, изчисляването на основните характеристики на графиката (свързаност, простота, Ойлер, пълнота, bipartition, редовността на графиката, и други подобни). Проверка плоскостенността и изоморфни графиките.
- Действия с графики. Добавяне или премахване върхове и ръбове на свързаните компоненти, сливане графиките на върховете, съюза, пресичане и декартови продукт съединение. Изграждане допълнение графика.
- Маршрути, вериги и цикли пътеки. Ойлер верига и Hamiltonian цикъл и проверка на графиката за изпълнение на тези свойства.
- характеристиките на изчисление на графиката. Разстояние: диаметърът на графиката, центъра на графика, радиус графика. Изчисляването на cyclomatic и хроматичната номер.
- Проблеми на графики. Най-кратък проблем път (Алгоритъм на Дейкстра, Белман, изграждане на пътя дърво). А строителството проблем минимум обхващаща дърво (алгоритъм Kruskal му). Максимална проблем поток в мрежа (Folkersona-Ford алгоритъм). Проблемът на графика оцветяване.
- Проучването на дървета (на специални видове графики без цикли). Дървета, използвани в криптиране, програмиране, както и много други приложения.
Задачи в колони с решение онлайн
Задача 1. изграждане на графика на връзката "х + у ≤7" на поставените = M. Определяне на свойствата му.
Задача 2. Намерете най-краткия път в насочен графиката от първия връх на всички други, използвайки Алгоритъм на Дейкстра. Изграждане на най-краткия път дървото.
Задача 3. Намерете максималният поток и минимално намаление на транспортната мрежа, като използва алгоритъм Ford-Fulkerson (бележки поставяне алгоритъм) Построява се графика на стъпки. За да проверите състоянието на максимална построен целия поток. Източник - връх 1, в канала - 8 върха.
Задача 4. Изграждане на обхващаща дърво минимално тегло, използвайки алгоритъм и Kruskal Prim е. С помощта на матрица Кирхоф получите номера (не-изоморфно) обхваща дървета с помощта на компютър математически пакети (например, MathCAD, Mathematica, MatLab).
Задача 5. Изисква се създаде структурна матрица за диграфа (или графиката) и техниките на Булева алгебра, да намерите по целия път от $ P_ $ $ $ аз върхове в връх $ к $, след това да търсят всички раздели $ s_ $ между тези върхове. В тази задача (за да се избегнат възможни неясноти графичен тираж) показват всички насочени ръбове и запис (2-4) означава, че двете свързани връх 4 минути, и не обратна връзка. Припомнете си, че за намиране на пътища от връх $ аз $ връх $ й $ оповестява малка структурна матрица $ $ М- (нулиране на структурната матрица с номера на брой ред $ й $ и колона $ аз $). Сеченията са също начини отрицание (връзка и дизюнкция е променен на обратното).
Цел 6. За графика $ G = (X, U) $ както следва:
1.1. изграждане на:
- близост матрица,
- честота матрица.
1.2. Определяне на степента на върхове $$ за всички на графиката.
Проблем 7. Намери всички кратки пътеки в насочено графика, като се използва алгоритъм Floyd.
Задача 8. Комплект $ G (X, GX) $
$ X = $,
GC:
= GX1, GX2 = GX3 = Gx4 = = Gx5.
Определяне на хроматичната и cyclomatic броя на графиката.
Задача 9. Ако приемем, че ненасочена графика, означават върховете и краищата и да се определят различни символи.
3.1. Местна среда и степента на всеки връх в близост структура;
3.2. Построява честота и съседство матрица;
3.3. Помислете част на графиката. Примери за частично графика, частичен графика покритие. Покажи подграф, състояща се от три върхове. Колко от тези подграфи може да се намери в тази графа? Показване примери пресичат и комбиниране на части от графиката;
3.4. Дайте примери за цикличен маршрут, верига, проста схема. Опитайте се да намерите обиколката Ойлер;
3.5. Определяне на центъра и радиуса на диаметъра на графиката.
Предвид графиката е насочено определи
3.6. степента на върхове
3.7. Честота матрица и близост.
3.8. Дайте примери за начините ориентирана верига, прост цикъл верига линия и прост цикъл.
Теорията на решение графика по поръчка
Провеждаме задачи, контрол и практически работи по всички раздели на теорията на графите. Подробен план, таблици, фигури, обяснение е възможно да се пишат програми на езици за програмиране (за графика алгоритми), или използването на специални програми. Разтворът на икономическите проблеми, свързани с графика теория.
Например, стойността на 100 рубли. дизайн, изработен в Word, за период от 2 дни. Също така съдейства за предоставянето на тестове на графики.
Поръчайте решаването на проблеми на теорията на графики лесно
Свързани статии