Diskrečioji matematika

Kauno technologijos universitetas

Informatikos fakultetas

Diskrečioji matematika

Atliko:

Dėstytoja:

Kaunas, 2002

1.

 Sudaryti algoritmą ir programą randančią visus grafus turinčius l ilgio Oilerio ciklą.

 Tai yra kombinatorikos ir grafų teorijos uždavinys. Jei grafas turi l ilgio Oilerio grandine, tai vadinasi grafo viršūnių laipsnių suma yra 2*l. Grafas gali turėti dvi nelyginio laipsnio viršūnes, bet tada jis turėtų Oilerio grandinę, o mums reikia rasti Oilerio ciklą. Todėl Norint suformuoti visus grafus, turinčius l ilgio Oilerio ciklą reikia skaičių 2*l išskaidyti visais galimais variantais (suformuoti grafo viršūnių laipsninę seką) iir patikrinti ar sugeneruotas grafas turi l ilgio Oilerio ciklą, t.y. patikrinti ar visos viršūnės yra lyginio laipsnio.

 Būtinumas. Tarkime G – Oilerio grafas. Oilerio ciklas eidamas per kiekvieną viršūnę, patenka į viršūnę viena briauna, o išeina – kita briauna. Tai reiškia, kad kiekviena grafo G viršūnė incidentiška lyginiam Oilerio ciklo briaunų skaičiui. Kadangi Oilerio ciklas apima visas grafo briaunas, tai reiškia, kad grafas yra jungusis ir, kad kiekvienos grafo viršūnės laipsnis yra lyginis

.

 Išskaidymas “žodyno” tvarka.

Išskaidyme komponentų tvarka nesvarbi. Skaičiaus n iišskaidymą galima užrašyti taip:

m1*p1, m2*p2, . . ., ml*pl,

čia mi rodo, kad komponentė pi į išskaidymą įeina mi kartų, t.y.

l

n =  mipi

i=1

pasinaudojant tokiu išskaidymo užrašymu generuojami išskaidymai, kur p1>p2 . . . >pl.

Skaičiaus n išskaidymas pradedamas nuo iišskaidymo {n*1}. Norėdami gauti nagrinėjamam išskaidymui {m1*p1, m2*p2, . . ., ml*pl} gretimą išskaidymą, nagrinėsime patį dešinyjį išskaidymo elementą mlpl.

Jei ml > 1, tai galime pašalinti du elementus pl ir įvesti dar vieną elementą pi+1 (arba įvesti vieną elementa pl+1, jei tokio elemento nagrinėjamu momentu nebuvo).

Jei ml = 1, tai suma ml-1 pl-1 + ml pl pakankamai didelė, kad galėtume įvesti dar vieną pl-1 + 1. Bet kuriuo atveju tas, kas lieka paverčiama į atitinkamą vienetukų skaičių.

 Skaičiaus n išskaidymų generavimo “žodyno” tvarka algoritmas

l=1;

p[-1]=0; m[-1]=0;

p[0]=n+1;

m[0]=0;

p[1]=1;

m[1]=n;

while (l!=0)

{Spausdinti(l);

sum= m[l]*p[l];

if (m[l]==1)

{l=l-1;

sum=sum+m[l]*p[l];

}

if (p[l-1]==p[l]+1)

{l=l-1;

m[l]=m[l]+1;

}

else {p[l]=p[l]+1;

m[l]=1;

}

if (sum > p[l])

{p[l+1]=1;

m[l+1]=sum – p[l];

l=l+1;

}

}

 Tikrinimas ar sugeneruotas grafas turi Oilerio grandinę

Patikrinama ar išskaidymas sudaro grafą, t.y.ar pirmos viršūnės laipsnis bent vienetu mažesnis už viršūnių skaičių. Suskaičiuojama kiek viršūnių išskaidyme turi nelyginį laipsnį. Jei tokių viršūnių yra lygiai dvi tai grafas turi Oilerio grandinę. Jei visos viršūnės turi lyginį laipsnį, tai grafas turi Oilerio ciklą.

//—–Ar grafo viršūnių laipsniai yra mažesni už———-

if (virs [1]

#pragma hdrstop

#include „Unit1.h“

//——————————————————————

#pragma package(smart_init)

#pragma resource „*.dfm“

TForm1 *Form1;

//——————————————————————

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//——————————————————————

void __fastcall TForm1::Button1Click(TObject *Sender)

{ Memo1->Clear();

briaunos = StrToInt(Edit1->Text); //Grafo briaunos

n = bbriaunos * 2; //Grafo viršūnių laipsnių suma du kartus didesnė

//nei briaunų skaičius

Memo1->Lines->Add(„Oilerio grafai turintys l ilgio Oilerio grandines“);

Memo1->Lines->Add(„Duotos grafo viršūnių laipsnių sekos. Kiekvienas sekos skaičius nurodo kokio laipsnio yra atitinkama viršūnė.“);

Isskaidymas();

}

//——————————————————————

void TForm1::Spausdinti(int l)

{ int i, j, k;

AnsiString Eil;

k = 1; // Suformuojamas viršūnių laipsnių masyvas

for (i=1; i<=l; i++)

for (j=1; j<=m[i]; j++)

{virs[k] = p[i];

k++;

}

if (Tikrinimas(k)) //Patikrinama ir jeigu tinka atspausdinama

{Eil = „“;

for (i=1; iLines->Add(Eil);

}

}

//——————————————————————

int TForm1::Tikrinimas(int kiek)

{ int nelyg;

if (virs [1] p[l])

{p[l+1]=1;

m[l+1]=sum – p[l];

l=l+1;

}

}

}

Testas 1

Duomenys

7

Pastaba. Skaičius įvedamas ekrane ir jis nurodo kokio ilgio Oilerio ciklą turi turėti sugeneruotas grafas.

Rezultatai

2 2 2 2 2 2 2

4 2 2 2 2 2

4 4 2 2 2

Viršūnių laipsnių seka: 2 2 2 2 2 2 2

Viršūnių laipsnių seka: 4 2 2 2 2 2

Viršūnių laipsnių seka: 4 4 2 2 2

Testas 2

Duomenys

6

Rezultatai

2 2 2 2 2 2

4 2 2 2 2

Viršūnių laipsnių seka: 2 2 2 2 2 2

Viršūnių laipsnių seka: 4 2 2 2 2