МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 7 На тему: “ Способи задання графів ” З дисципліни : " Дискретна математика" Лектор: Сердюк П.В. Прийняв: Львів – 2007 Завдання: Використовуючи даний спосіб представлення графа, ввести з клавіатури граф, зберегти його даним способом, і вивести на екран за допомогою графічних функцій, із вказанням номерів дуг (ребер, вершин). У випадку орієнтованого графа, вказати напрямок дуг. Сформулювати переваги та недоліки даного способу представлення графу з алгоритмічної точки зору. Звіт оформити за вимогами шаблону. Варіант 5. Матриця інциденцій. Псевдограф. Текст програми uses crt, graph; var driver,i,j,z,n,p, mode: integer; x1,x2,x3,x4,y1,y2,y3,y4,e:integer; a:array [1..20,1..100] of integer; flag:array[1..10] of boolean; begin clrscr; writeln('Vvedit kilkist reber'); readln(n); if n>0 then begin writeln('Chi zyrdnana vershyna z rebrom?'); writeln('1 - Tak, 0 - Hi'); end; for i:=1 to 4 do for j:=1 to n do begin write('V[',i,']E[',j,']'); readln(a[i][j]); while (a[i][j]<0)or(a[i][j]>1) do begin writeln('Treba vvodutu 0 abo 1 !!!!'); writeln('Chi zyrdnana vershyna ',i,' z rebrom ',j,'?'); readln(a[i][j]); end; end; for i:=1 to 4 do begin writeln; for j:=1 to n do write(a[i][j],' '); end; readln; driver:=detect; initGraph(driver, mode,'f:\programs\tp71\bgi'); repeat x1:=180;x2:=400;x3:=x1;x4:=x2; y1:=150;y4:=350;y2:=y1;y3:=y4; setcolor(15); circle(x1,y1,2); putpixel(x1,y1,15); outtextxy(x1-3,y1+10,'1'); circle(x2,y2,2); putpixel(x2,y2,15); outtextxy(x2-3,y2+10,'2'); circle(x3,y3,2); putpixel(x3,y3,15); outtextxy(x3-3,y3-15,'3'); circle(x4,y4,2); putpixel(x4,y4,15); outtextxy(x4-3,y4-15,'4'); setcolor(15); for j:=1 to n do begin p:=0; for i:=1 to 4 do if a[i][j]=1 then inc(p); if p=1 then begin if a[1,j]=1 then begin circle(x1-6,y1-7,10); end; if a[2,j]=1 then begin circle(x2+6,y2-7,10); end; if a[3,j]=1 then begin circle(x3+6,y3+7,10); end; if a[4,j]=1 then begin circle(x4-6,y4+7,10); end; end else if p=2 then if (a[1,j]=1)and(a[2,j]=1)and(flag[1]=false) then begin line (x1,y1,x2,y2);flag[1]:=true; if (a[1,j+1]=1)and(a[2,j+1]=1) then begin setcolor(green);line (x1,y1,x2,y2);end; if (a[1,j+2]=1)and(a[2,j+2]=1) then begin setcolor(red);line (x1,y1,x2,y2); end; end; setcolor(15); if (a[1,j]=1)and(a[3,j]=1)and(flag[2]=false) then begin line (x1,y1,x3,y3);flag[2]:=true; if (a[1,j+1]=1)and(a[3,j+1]=1) then begin setcolor(green);line (x1,y1,x3,y3);end; if (a[1,j+2]=1)and(a[3,j+2]=1) then begin setcolor(red);line (x1,y1,x3,y3); end; end; setcolor(15); if (a[1,j]=1)and(a[4,j]=1)and(flag[3]=false) then begin line (x1,y1,x4,y4);flag[3]:=true; if (a[1,j+1]=1)and(a[4,j+1]=1) then begin setcolor(green);line (x1,y1,x4,y4);end; if (a[1,j+2]=1)and(a[4,j+2]=1) then begin setcolor(red);line (x1,y1,x4,y4); end; end; setcolor(15); if (a[2,j]=1)and(a[3,j]=1)and(flag[4]=false) then begin line (x2,y2,x3,y3); flag[4]:=true; if (a[2,j+1]=1)and(a[3,j+1]=1) then begin setcolor(green);line (x2,y2,x3,y3);end; if (a[2,j+2]=1)and(a[3,j+2]=1) then begin setcolor(red);line (x2,y2,x3,y3); end; end; setcolor(15); if (a[2,j]=1)and(a[4,j]=1)and(flag[5]=false) then begin line (x2,y2,x4,y4); flag[5]:=true; if (a[2,j+1]=1)and(a[4,j+1]=1) then begin setcolor(green);line (x2,y2,x4,y4);end; if (a[2,j+2]=1)and(a[4,j+2]=1) then begin setcolor(red);line (x2,y2,x4,y4); end; end; setcolor(15); if (a[3,j]=1)and(a[4,j]=1)and(flag[6]=false) then begin line (x3,y3,x4,y4); flag[6]:=true; if (a[3,j+1]=1)and(a[4,j+1]=1) then begin setcolor(green);line (x3,y3,x4,y4);end; if (a[3,j+2]=1)and(a[4,j+2]=1) then begin setcolor(red);line (x3,y3,x4,y4); end; end; end; setcolor (white); outtextxy(500,350,'white - 1'); setcolor(green); outtextxy(500,380,'green - 2'); setcolor(red); outtextxy(500,410,'red - 3'); until keypressed; closegraph; end. Висновок: На цій лабораторній роботі я освоїв способи задання грагів.