Graflar u’stinde a’meller Graflar u’stinde apiwayi a’meller

7- mi’sal. 8- su’wrette to’beleri ko’plikleri kesilispeytug’in ha’m graflardi’n’ ko‘beymesi a’meli su’wretlengen.
Graflardi’ ko‘beytiriw a’melin ta’krar qollaw usili menen graflar teoriyasinin’ a’hmiyetli klasin du’ziwshi o‘lshemli kubladni ani’qlaw mu’mkin. o‘lshemli kub ( ) to’beleri sani ekige ten’ bo‘lgan toli’q graf ja’rdeminde to’mendegi rekurrent formula menen aniqlanadi:
, .
Joqarida graflar u’stindegi ayrim a’meller haqqinida qisqasha mag’li’wmat berildi. Soni esletiw kerek, graflar u’stinde bunnan basqa bir qatar a’meller de bar.
Marshrutlar ha’m shinjirlar
Marshrutlar ha’m shinjirlar haqqi’nda uliwma mag’li’wmatla . To’beleri ko’pligi ha’m qabi’rg’alar korteji bolg’an oriyentirlenbegen graf berilgen bolsi’n. Bul grafdag’i to’beler ha’m qabi’rg’alardi’n’ ha’r eki qon’si’ qabi’rg’alari uliwma shetki to’bege iye

ko‘rinisdegi shekli yaki sheksiz izbe-izligi marshrut dep ataladi’. Marshrutti onin’ to’beleri izbe-izligi yaki qabi’rg’alari izbe-izligi ko‘rinisinde de belgilew mu’mkin.
Eger marshrutta qanday da to’beden aldin to’beler bolsa’ykes a, bul to’beni marshrutti’n’ baslang‘ish to’besi dep, usi to’beden keyin marshrutqa tiyisli to’beler bolmag’anda bolsa , oni marshrutti’n’ aqi’rg’i’ to’besi dep ataydilar.
Eger marshrutti’n’ baslang‘ish to’besi ha’m aqi’rg’i’ to’besi bolsa, onda oni to’beden to’bega bag’itlang’an marshrut yaki shetleri ha’m bolg’an marshrut dep ataladi’.
Marshrutdag’i eki qon’si’ qabi’rg’alarg’a tiyisli to’be ishki to’be yaki araliq to’be dep ataladi’.
Marshrutta qabi’rg’alar ha’m to’beler ta’krarlaniwi mu’mkin bolg’ani to’besin marshrutti’n’ ishki to’besi, bir waqi’t ti’n’ o’zinde , onin’ baslang’ish ha’m (yaki) aqi’rg’i’ to’besi boli’wi’ da mu’mkin ha’m kerisi , marshrutti’n’ baslangish ha’m(yaki) aqi’rg’i’ to’besi onin’ ishki to’besi boli’wi’ da mu’mkin.
Bizge belgili, marshrut:
– baslang’ish to’bege da aqi’rg’i’ to’bege da iye bolmawi mu’mkin(bunday marshrut eki ta’repleme sheksiz marshurt dep ataladi’);
– baslang’ish to’bege iye bolip, aqi’rg’i’ to’bege iye bolmawi mu’mkin yaki, kerisinshe , aqi’rg’i’ to’bege iye bolip , baslang’ish to’bege iye bolmawi mu’mkin (bir ta’repleme sheksiz marshrut);
– jalg’iz qabi’rg’adan ibarat boli’wi’ mu’mkin (notrivial marshrut);
– hesh bir qabi’rg’ag’a iye bolmawi mu’mkin (no’l marshrut yoki trivial marshrut).