Съществуват различни начини за представяне на графи

Съществуват различни начини за представяне на графи.

Вторият начин е чрез списъци на съседите (синовете за ориентирания случай) – за всеки връх задаваме множество (за мултиграф задаваме списък, в който може да има повторения) от неговите съседи (синове).

За третия начин дефинираме матрица на съседство за краен ориентиран мултиграф G (V, E, f_G) – M_G =,

a_ij = |{ e |e  E, f_G (e) = (v_i, v_j) } |. При неориентирани графи не

отчитаме примките, т.е. a_ii = 0 за i = 1, 2, …, |V|. Ясно е, че при краен неориентиран мултиграф G матрицата M_G е симетрична и с нули по диагонала, при неориентирани графи тя е двоична, а при мултиграфи елементите са произволни естествени числа.
Тъй като всяко дърво е граф, то за представяне на дървета можем да използваме начините за представяне на графи. Съществуват, обаче, много по-ефективни представяния. Например, всяко кореново дърво D (V, E) с корен r може да бъде представено със списък на бащите: едномерен масив p с |V| елемента,

като p[v] е върхът, към който е присъединен върха v (бащата на v), по дефиниция p[r] = 0 – несъществуващ връх.

 (v) – разклоненост на v като броят на синовете на v. Максималната разклоненост на върховете в едно кореново дърво наричаме разклоненост на дървото. Кореново дърво с разклоненост 2 наричаме двоично дърво, с разклоненост 3 троично дърво и т.н. с разклоненост m m-ично дърво.

Във всяко двоично дърво може условно да се въведе наредба на синовете – ляв и десен син. По този начин двоичните дървета удобно се представят чрез наредба на синовете – за всеки връх се задава наредена двойка от синовете му – (ляв син, десен син), отсъствието на син задаваме например с 0.
Съвсем аналогично можем да въведем условна наредба на синовете и в m-ично дърво и да представяме m-ичните дървета с наредени m-торки от синове, но това е твърде неефективно, тъй като в таблицата ще има много празни полета. Затова ще разгледаме едно друго представяне.

Нека в кореновото дърво D е въведена наредба на синовете. Съвкупността от всички синове на даден връх ще наричаме братство. Първият син в братството наричаме най-ляв син, а съседът на всеки син, който стои непосредствено отдясно наричаме десен брат. Ясно е, че последният в братството няма десен брат. За коренови дървета с по-голяма разклоненост може да се използва представянето, наречето “най-ляв син, десен брат” – това е списък от наредени двойки, по една за всеки връх, на първо място стои най-левия син на дадения връх (0, ако няма синове), а на второ място стои десният брат на върха (0, ако той е последен в братството).

два типа данни: Nat и Bool. Nat са естествените числа, в Bool има две стойности tt - истина и ff - лъжа. Ще считаме, че разполагаме с определен набор от основни операции oт следните видове:

• 
  операции f : Natⁿ  Nat, n  1, например събиране (+),
  

• 
  операции f : Natⁿ  Bool, n  1, например равенство (=), различните видове неравенства (<, , >, ) и т.н.;
  
• 
  операции f : Boolⁿ  Bool, n  1, например конюнкция (&), дизюнкция (), отрицание () и т.н.
  

Синтактичните елементи на езика са следните:

• 
  константи от тип Nat и Bool за означаване на елементи
  

• 
  символи за основните операции;
  
• 
  обектови променливи, които ще означаваме с главните букви
  

• 
  функционални променливи, които ще означаваме с F_kⁿ, където k е индекс, променливата F_kⁿ ще приема стойност частична функция над Nat, n указва броят на аргументите на функцията;
  
• 
  точки, запетаи, скоби, чрез които ще постигаме еднозначен синтактичен анализ.
  

Дефинираме индуктивно понятието терм от тип Nat.

База:

1. 
   Всяка константа от тип Nat е терм от тип Nat.
   
2. 
   Всяка обектова променлива е терм от тип Nat.
   

Стъпка:

1. 
   Ако f : Natⁿ  Nat е основна операция, то f (₁, ₂, …, _n) е терм от тип Nat.
   
2. 
   Ако F_kⁿ е функционална променлива, то F_kⁿ (₁, ₂, …, _n) е терм от тип Nat.
   

Дефинираме индуктивно понятието терм от тип Bool.

База:

1. 
   Всяка константа от тип Bool е терм от тип Bool.
   
2. 
   Ако f : Natⁿ  Bool е основна операция и ₁, ₂, …, _n са термове от тип Nat, то f (₁, ₂, …, _n) е терм от тип Bool.
   

Стъпка: Ако f : Boolⁿ  Bool е основна операция, то f (₁, ₂, …, _n) е терм от тип Bool.

₁, ₂ са термове от тип Nat. Тогава if  then ₁ else ₂ е условен терм.

 (X₁, …, X_n, , , …, ) за да укажем, че обектовите променливи на  са сред X₁, …, X_n, а функционалните променливи на  са сред , , …, . Понякога ще използваме съкратен запис  (X, F). Също, ще си позволяваме да изпускаме броя на аргументите за една функционална променлива, ако той не е съществен.

Означаваме с  (X₁/₁, X₂/₂, …, X_n/_n, F) термът, който се получава от  чрез едновременно заместване на всяка от обектовите променливи X₁, …, X_n с термовете ₁, …, _n съответно. Понякога ще използваме съкратен запис  (X/, F).

₀ (X₁, …, X_n, , , …, ), where

…

(X₁, …, ) = _k (X₁, …, , , , …, )

Тук ₀ е терм от тип Nat, ₁, …, _k са термове от тип Nat или условни термове.
Ще определим операционната семантика на една програма R.
Нека  е функционален терм. Израз от вида   c, където c е константа от типа на  наричаме опростяване на 

в програмата R.

Ще дефинираме правила, по които ще се извършва опростяването.

0. 
   c  c за всяка константа c (от тип Nat или от тип Bool).
   
1. 
   Нека f е n-местна основна операция, ₁, …, _n са функционални термове, ₁  c₁, ₂  c₂, …, _n  c_n и
   

0. 
   Нека  е функционален терм от тип Bool, ₁, ₂ са функционални термове от тип Nat.
   
   1. 
      Нека   tt и ₁  c. Тогава if  then ₁ else ₂  c.
      
   2. 
      Нека   ff и ₂  c. Тогава if  then ₁ else ₂  c.
      

1  i  k.

Нека ₁  c₁, ₂  c₂, …,  .

Нека _i (X₁/c₁, X₂/c₂, …, /, , , …, )  c.

Тогава (₁, ₂, …, )  c.
От вида на правилото 3. следва, че преди да предадем параметрите на дадена подпрограма трябва задължително да намерим техните стойности.
Казваме, че опростяването   c е изводимо по стойност в

програмата R и отбелязваме R   c, ако съществува крайна редица S₀, S₁, …, S_n от множества от опростявания, такава че:

1. 
   S₀ = ,   c  S_n.
   
2. 
   За всяко i = 0, 1, …, n-1 имаме, че S_i+1 = S_i  {   c}, където опростяването   c e извършено по правило 0. или по едно от правилата 1., 2., 3. с предпоставки елементи на S_i.
   

Числото n наричаме дължина на извода за опростяването   c.

1. 
   Ако  е константа, то  = c.
   
2. 
   Ако  = f (₁, ₂, …, _n), то съществуват константи c₁, c₂, …, c_n, такива че R _i  c_i, i = 1, 2, …, n, при това с дължина на изводите по-малка от k и f (c₁, c₂, …, c_n) = c.
   
3. 
   Ако  = if  then ₁ else ₂, то R   tt и R ₁  c
   

4. 
   Ако  = (₁, ₂, …, ), то съществуват константи
   

Нека  е функционален терм, c₁ и c₂ са константи от типа на  и

Функцията O_V (R) наричаме операционна семантика на програмата R с предаване по стойност.

Определението е коректно, т.е. O_V (R) действително е функция, тъй като е в сила еднозначност на опростяването по стойност.
Нека A e произволно множество, в което е въведена частична наредба . Нека съществува   A, който е най-малък относно , т.е.   a за всяко a  A. Нека, освен това, всяка монотонно растяща редица а₀  а₁  …  a_n  …има точна горна граница в A, т.е. съществува a  A, такова че a_n  a за всяко n   и за всяко

b  A, такова че a_n  b за всяко n   имаме, че a  b. Естествено, точната горна граница a  А е единствена, означаваме a = . При тези предположения, наредената тройка (A, , ) наричаме област на Скот.

В множеството F_n въвеждаме частична наредба:

(f, g  F_n) f  g  за всяко x  ⁿ, y   имаме f (x)  y  g (x)  y. Ако f  g, казваме че f е подфункция на g или, че g е продължение на f. Наредбата притежава най-малък елемент – никъде дефинираната функция, която ще означаваме с ! – тя се продължава до всяка функция.
Твърдение: Нека { f_k} е монотонно растяща редица от

функции, f_k  F_n. Дефинираме функцията g по следния начин:

(x  ⁿ, y  ) g (x)  y  съществува k  , такова че f_k (x)  y.

Тогава g е добре дефинирана n-местна функция, която е точна горна граница на { f_k }.

Доказателство: Тривиална проверка.
Като следствие тройката F_n = (F_n, , !) е област на Скот.
Нека A₁ = (A₁, ₁, ₁), A₂ = (A₂, ₂, ₂), …, A_n = (A_n, _n, _n), n  2 са области на Скот. Означаваме A = A₁ x A₂ x … x A_n – декартовото произведение на множествата A₁, A₂, …, A_n.

В A въвеждаме релация  : за всеки a_i  A_i, b_i  A_i, i = 1, 2, …, n,

(a₁, a₂, …, a_n)  (b₁, b₂, …, b_n)  a₁ ₁ b₁ и a₂ ₂ b₂ и …и a_n _n b_n.

Очевидно е, че  е частична наредба в А. При това

 = (₁, ₂, …, _n) е най-малък елемент в A относно .
Твърдение: Нека { (a_k¹, a_k², …, a_kⁿ) } е монотонно растяща редица от елементи на A. Нека a_i  A_i е точната горна граница на { a_kⁱ},

i = 1, 2, …, n. Тогава (a₁, a₂, …, a_n)  A е точна горна граница на

редицата { (a_k¹, a_k², …, a_kⁿ) }.

Доказателство: Тривиална проверка.

A = A₁ x A₂ x … x A_n,  е дефинираната частична наредба,

 = (₁, ₂, …, _n). Тази област на Скот наричаме декартово произведение на областите на Скот A₁, A₂, …, A_n.
Нека A₁ = (A₁, ₁, ₁), A₂ = (A₂, ₂, ₂) са области на Скот.

Казваме, че изображението f : A₁  A₂ е непрекъснато, ако за всяка монотонно растяща редица a₀ ₁ a₁ ₁ …₁ a_n ₁ …от елементи на A₁ имаме, че f () е точна горна граница на редицата { f (a_n)} в A₂.

Казваме, че изображението f : A₁  A₂ е монотонно, ако

за всеки a, b  A₁ имаме a ₁ b  f (a) ₂ f (b).

Доказателство: За всеки a, b  A₁ и a ₁ b разглеждаме монотонната редица a, b, b, …и използваме непрекъснатостта.

a₀ ₁ a₁ ₁ …₁ a_n ₁ …е монотонно растяща редица в A₁, то

f (a₀) ₂ f (a₁) ₂ …₂ f (a_n) ₂ …е монотонно растяща редица в A₂ и

f () = .

Нека A = (A, , ), A_i = (A_i, _i, _i), i = 1, 2, …, n са области на Скот.
Твърдение: Нека f_i : A  A_i са непрекъснати изображения,

i = 1, 2, …, n. Дефинираме изображение

f₁ x f₂ x …f_n : A  A₁ x A₂ x … A_n,

(f₁ x f₂ x …f_n)(a) = (f₁ (a), f₂ (a), …, f_n (a)) за всяко a  A.

Твърдим, че f₁ x f₂ x …x f_n е непрекъснато.

Доказателство: Тривиална проверка.

Казваме, че a  A е неподвижна точка на f, ако f (a) = a.

Казваме, че a  A е най-малка неподвижна точка на f, ако

f (a) = a и за всяко b  A, такова че f (b) = b имаме a  b.

Естествено, ако f притежава най-малка неподвижна точка, тя е единствена.

Казваме, че a  A е квазинеподвижна точка на f, ако f (a)  a.

Казваме, че a  A е най-малка квазинеподвижна точка на f,

ако f (a)  a и за всяко b  A, такова че f (b)  b имаме a  b.

Естествено, ако f притежава най-малка квазинеподвижна точка, тя е единствена.