Міністерство освіти і науки
України
Житомирський державний
технологічний університет
ФІКТ, Кафедра ПЗОТ, група ПІ-39
Лабораторна робота
з дисципліни «Дискретна
математика»
на тему: «Способи зберігання графів.
Пошук в графі»
Виконала:
Перевірив:
Житомир 2010
Завдання
зберігання
граф програмний пошук
І. Подати на вхід.txt
файл з матрицею суміжності.
1. Зчитування з
файлу.
2. Обробка
А) Перевірка на:
– орієнтованості;
– симетричність;
Б) Формування
матриці інциденцій.
ІІ. Забезпечити
пошук в глибину і в ширину графа.
- Визначити
зв’язність графу.
- Визначити
розбиття вершин на класи еквівалентності за відношенням «зв’язність».
- На вхід подати
матрицю суміжності графу.
Порядок
виконання роботи
1. Складемо
програму для виконання зчитування та обробки графів. Лістинг програми з
відповідними коментарями наведено нижче.
Код програми:
#include
<conio.h>
#include
<stdio.h>
#include
<stdlib.h>
#include
<iostream.h>
#define m 10
int main (void){
clrscr();
int
count,i,j,l=0,s=0,g=0,z;
int h=0;
int M[m][m];
int a[m][m];
int b[m][m];
FILE* file;
if ((file =
fopen("matr.txt", "rt"))== NULL){
fprintf(stderr,
"Cannot open input file.n");
return 1; }
cout<<"Matrytsay
sumizhnosti: "<<endl;
fscanf(file,"%d",&count);
cout<<"Rozmir
matrusti: "<<count<<"x"<<count;
for(i=0;i<count;i++){
cout<<endl;
cout<<"ttt";
for(j=0;j<count;j++)
{
fscanf(file,"%d",&M[i][j]);
cout<<M[i][j]<<"
";
}
}
int k=0;
for(i=0;i<count;i++)
for(j=0;j<count;j++)
if(M[i][j]!=M[j][i])
k=1;
if(k!=1)
cout<<"nGraf
ne orientovanuy." ;
else
cout<<"nGraf
orientovanuy.";
//----------------------
if (k==1){
for(i=0;i<count;i++)
for(j=0;j<count;j++)
if(M[i][j]==1)
l++;
for(i=0;i<count;i++)
for(j=0;j<l;j++)
a[i][j]=0;
cout<<endl<<endl;
l=0;
for(i=0;i<count;i++)
for(j=0;j<count;j++)
if(M[i][j]==1){
l++;
if(i==j)
a[i][j]=2;
else{
a[i][l-1]=-1;
a[j][l-1]=1;
}
}
cout<<"Matrica
incudentnosti: n";
for(i=0;i<count;i++){
cout<<endl;
for(j=0;j<l;j++)
cout<<a[i][j]<<"t";
}
}
if (k!=1){
for(i=0;i<1;i++)
for(j=0;j<count;j++)
if(M[i][j]==1)
s++;
for(i=1;i<count;i++)
for(j=i+1;j<count;j++)
if(M[i][j]==1)
g++;
s=g+s;
cout<<"ns="<<s;
for(i=0;i<count;i++)
for(j=0;j<s;j++)
b[i][j]=0;
cout<<endl<<endl;
z=s;
s=0;
for(i=0;i<count;i++)
for(j=i;j<count;j++)
if(M[i][j]==1){
s++;
b[i][s-1]=1;
b[j][s-1]=1;
}
cout<<"Matrica
incudentnosti";
for(i=0;i<count;i++){
cout<<endl;
for(j=0;j<z;j++)
cout<<b[i][j]<<"t";
}
}
//--------------------------------------------------------------------
cout<<"nnSpuski
sumiznosti:"<<endl;
for(i=0;
i<count; i++){
cout<<i+1<<":
";
for(j=0;
j<count; j++){
if(M[i][j]==1){
cout<<j+1<<"
";}
}
cout<<endl;
}
getch();
return 0;}
2. Складемо
програму для виконання пошуку в графі, визначення його зв’язності та розбиття.
Лістинг програми з відповідними коментарями наведено нижче.
Код програми:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream.h>
typedef struct
list
{
int number;
struct list
*next;
}list;
void Depth(int
v);
void Width(int
v,int n);
list*
AddElem(list *last, int i,int j);
list **V;
int* NEW;
void main()
{
clrscr();
FILE *file;
int
i,j,n,M[10][10],a,v,count=0 ;
if((file=fopen("input.txt","rb"))
== NULL)
{
cout<<"nttttError
open!!!";
getch();
exit(1); }
fscanf(file,"%d",&n);
for(i=0;i<n;i++)
*NEW=1;
list *end,*pel;
/* vydilenya
pamyati dlya vkazivnykiv na spysky */
V= (list**)malloc(n
* sizeof (list*));
for(i=0;
i<n;i++)
V[i] = (list*)malloc(sizeof
(list));
for(i=0;i<n;i++)
// obnulennja pokazh4ukiv v kinci spusky
V[i]=NULL;
for(i=0;i<n;i++)
//formuv spuskiv symizh
{
end=NULL;
for(j=0;j<n;j++)
{
fscanf(file,"%d",&a);
M[i][j]=a;
if(a==1)
{
end=AddElem(end,i,j);
}
}
}
cout<<"Depth
search:";
for(i=0;i<n;i++)
{
v=i;
pel=V[v];
while(pel!=NULL)
{
if(NEW[v])
{
count++;
Depth(v);
printf("nn");
}
pel=pel->next;
v=pel->number-1;
}
}
cout<<"Kilkist
komponent zviaznosti:"<<count;
if(count>1)
cout<<"nGraf
ne zvyaznyyn";
else
cout<<"nGraf
zvyaznyyn";
cout<<"n-------------------------------n";
for(i=0;i<n;i++)
NEW[i]=1;
cout<<"nWidth
search:";
count=0;
for(i=0;i<n;i++)
{
v=i;
pel=V[v];
while(pel!=NULL)
{
if(NEW[v])
{
count++;
Width(v,n);
cout<<"nn";
}
pel=pel->next;
v=pel->number-1;
}
}
cout<<"Kilkist
komponent zvyaznosti:"<<count;
if(count>1)
cout<<"nGraf
ne zvyaznyyn";
else
cout<<"nGraf
zvyaznyyn";
cout<<"n-------------------------------nn";
cout<<"Spuski
sumiznosti:"<<endl;
for(i=0; i<n;
i++){
cout<<i+1<<":
";
for(j=0; j<n;
j++){
if(M[i][j]==1){
cout<<j+1<<"
";}
}
cout<<endl;
}
getch();
}
list*
AddElem(list *last,int i,int j)
{
list *pel;
pel=(list*)malloc(sizeof(list));
pel->number=j+1;
pel->next=NULL;
if(V[i]==NULL)
V[i]=pel;
else
last->next=pel;
return pel;
}
void Depth(int v)
{
int u;
list *pel=V[v];
cout<<v+1<<"
";
NEW[v]=0;
u=pel->number;
while(pel!=NULL)
{
if(NEW[u-1])
Depth(u-1);
pel=pel->next;
u=pel->number;
}
}
void Width(int
v,int n)
{
int
beg,end,*q,i,p,u;
list *pel;
q=(int*)malloc(n
* sizeof(int));
for(i=0;i<n;i++)
q[i]=0;
beg=end=0;
q[end]=v;
end++;
NEW[v]=0;
while(beg!=end)
{
p=q[beg];
for(i=0;i<end;i++)
q[i]=q[i+1];
end--;
cout<<p+1<<"
";
pel=V[p];
u=pel->number;
while(pel!=NULL)
{
if(NEW[u-1])
{
q[end]=u-1;
end++;
NEW[u-1]=0;
}
pel=pel->next;
u=pel->number;
}}}
Висновок
Виконуючи дану
лабораторну роботу я навчилась програмній роботі з графами, а саме операціям їх
зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість.
Крім того, було освоєно основи пошуку в графі в двох напрямках: (в глибину і в
ширину), а також визначено зв’язність графу, виконано розбиття множини вершин
на класи еквівалентності за відношенням «зв’язність».
Другие работы по теме:
Проектування реконструкції залізниць
Міністерство транспорту та зв‘язку України Державний економіко-технологічний університет транспорту Кафедра: «Реконструкція та експлуатація залізниць і споруд»
Сучасна митно-тарифна політика України
Особливості формування національної макромоделі зовнішньоекономічної політики. Поняття і основні форми митного контролю. Порядок зберігання підприємствами товарів та інших предметів, ввезених на митну територію України. Оформлення декларації-зобов'язання.
Реєстрація документів
Журнальна та карткова форми реєстрації документів, соціальні функції управління. Проставляння при реєстрації порядкових номерів і необхідних умовних позначень. Систематизація реєстраційно-контрольних карток, основні ознаки систематизації карток.
Морська капуста
Реферат на тему: “Морська капуста” Морська капуста – Laminaria Цукрова ламінарія – Laminaria saccharina Японська ламінарія – Laminaria japonica aresch
Розвязування задач за допомогою графів
МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ МАЛА АКАДЕМІЯ НАУК УКРАЇНИ ЖИТОМИРСЬКЕ ТЕРИТОРІАЛЬНЕ ОБ’ЄДНАННЯ ВІДДІЛЕННЯ: МАТЕМАТИКИ СЕКЦІЯ: ПРИКЛАДНА МАТЕМАТИКА
Зберігання продуктів. Домашнє консервування
Причини псування харчових продуктів. Способи зберігання та домашнього консервування харчових продуктів. Основні правила консервування. Припинити життєдіяльність мікроорганізмів, зруйнувати ферменти і запобігти псуванню харчових продуктів можна консервуван
Професійні вимоги до кухаря
Професійні вимоги до кухаря Кваліфікація - 3 розряд (рівень кваліфікації – розряд, клас, категорія) Кваліфікаційні вимоги Повинен знати: види, властивості, кулінарне призначення та особливості обробки картоплі, овочів, грибів, м'яса, риби, птиці, дичини, круп, макаронних виробів і бобових, сиру, яєць, тіста, консервів, концентратів та інших продуктів, ознаки та органолептичні методи визначення їх доброякісності, терміни та умови їх зберігання; способи, методи та форми нарізання овочів і зелені; технологію виготовлення котлетної маси з м'яса, риби та напівфабрикатів з неї; прийоми, способи та послідовність виконання теплового оброблення продуктів; правила реалізації, відпуску (комплектації) готової продукції, терміни та умови зберігання страв; рецептури, технологію виготовлення, вимоги до якості варених, смажених, запечених овочів, страв з круп, макаронних виробів і бобових,
Інформація та інформаційні процеси
Інформація та інформаційні процеси, носії інформації, властивості, форми і способи її подання, кодування повідомлень. Інформаційні процеси: пошук, зберігання, збирання, опрацювання, подання, передавання, використання, захист та сучасні засоби зберігання.
Моделі і методи прийняття рішень
Планування цілеспрямованих дій і прийняття рішень. Характеристика методу повного перебору - універсального методу вирішення оптимізаційних задач, якщо множина допустимих рішень обмежена. Експоненційна складність евристичного пошуку. Складність алгоритмів.
Створення програми "Шаховий кінь"
Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.
Пошук найкоротшого шляху на орієнтованому графі
Програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа. Загальні відомості про графи. Особливості роботи в середовищі. Опис структури програми та програмних засобів. Схема програмної реалізації алгоритму Дейкстри.
Системний аналіз складних систем управління
Основні положення системного аналізу, його використання. Характеристика та основні ознаки складних систем. Використання теорії графів для структурного аналізу. Графова потокова модель технологічного комплексу. Виділення внутрішніх комплексів в ТК.
Допоміжні алгоритми
та тему: ДОПОМІЖНІ АЛГОРИТМИ Тема: Допоміжні алгоритми. Мета уроку: навчити учнів складати допоміжні алгоритми; виховати старанність, дисциплінованість;
Аналіз топологій
Графічний, матричний та алгебраїчний способи задання топологій. Методи виявлення та перетворення топологічних структур. Перевага аналітичних способів задання топологій систем у теоретичних дослідженнях - компактність запису у вигляді системи формул.
Зовнішня та внутрішня винагорода Роль винагороди у мотивації
Задача менеджера, у випадку застосування економічної мотивації, полягає в розробці преміальної схеми виплат за продуктивність, системи відрядної оплати або трудових угод. Ця задача аж ніяк не проста, тому що ситуація в кожній фірмі унікальна і, отже, преміальна система повинна бути унікальної для кожного випадку.
Облік товаро-матеріальних цінностей
2.Облік товарів за групами. 3.Облік руху тари. 4.Облік допоміжних матеріалів. Облік в аптечних установах повинен забезпечувати безперервний і ретельний нагляд за наявністю, рухом, раціональним використанням та економним витрачанням матеріальних цінностей. Умови транспортування, зберігання та реалізації товарів аптечного асортименту потребують щоденного контролю і з боку працівників обліку, з тим щоб запобігти втратам, псуванню та розладнанню.
Алгоритм Дейкстра
Курсова робота З дисципліни” Основи дискретної математики” На тему: Алгоритм Дейкстра Зміст 1.Вступ …………………………………………………………………………………..…………3 2.Елементи теорії графів:
Метод орієнтованих графів
Лекція 37 . Можна виключити вершину . Для цього стрілки продовжують так, ніби вузла і не було. В діамагнетику вказується - коефіцієнт при виключеній вершині.
Порядок зберігання на складі Контроль терміну придатності
Особливості зберігання лікарських рослин сировини. Лікарська рослинна сировина повинна зберігатися в сухому, добре вентильованому приміщенні, в чистій сухій, без сторонніх запахів та однорідний для кожної партії сировині тарі, в аптеках – скляній, металічній, в ящиках з кришкою, на складах в паках, мішках паперових багатошарових або тканинних ящиках.
Подорожник 2
Реферат з біології на тему: Подорожник” Листя подорожника великого – Folium plantaginis majoris Подорожник великий – Plantago major l. Родина подорожникових
Типи алгоритмів
Способи запису алгоритмів. Блок-схеми і правила зображення блок-схеми. Типи алгоритмів. Складання блок-схем. Способи запису алгоритмів. Використовують такі способи подання (опису) алгоритмів:
Математичне забезпечення САПР
Тема : . Загальні поняття та вимоги до МЗ. Способи отримання математичних моделей. Постановка задач оптимізації. Класифікація і характеристика методів оптимізації.
Суть та елементи товароруху
Реферат на тему: Суть та елементи товароруху Товарорух - це система, яка забезпечує фізичне переміщення товарів і послуг від виробника до споживача, зокрема транспортування, зберігання, здійснення угод, передачу права власності, управління каналами збуту та сервісне обслуговування.