Кіріспе

Бағытталмаған, жалғасқан және ациклді график

Графтар теориясында ағаш – кез келген екі төбесі дәл бір жолмен жалғасқан, немесе балама түрінде жалғасқан ациклді бағытталмаған график. Орман – кез келген екі төбесі ең көп дегенде бір жолмен байланысқан бағытталмаған график немесе, балама түрінде, ациклді бағытталмаған график немесе, балама түрінде, ағаштардың бірікпеген жиыны. Бағытталған ағаш, бағдарланған ағаш, полиағаш немесе бір байланысты желі – бағытталған ациклді график (DAG), оның негізгі бағытталмаған графигі ағаш болып табылады. Полиорман (немесе бағытталған орман немесе бағдарланған орман) – бағытталған ациклді график, оның негізгі бағытсыз графигі орман. Компьютер ғылымында ағаш деп аталатын әртүрлі дерек құрылымдарының негізгі графиктері графтар теориясындағы ағаштар болып табылады, бірақ мұндай дерек құрылымдары көбінесе тамырланған ағаштар болып табылады. Тамырланған ағаш бағытталған болуы мүмкін, оны бағытталған тамырланған ағаш деп атайды, оның барлық қабырғалары тамырдан алыстатылған жағдайда, ол арборесценция немесе шығу ағашы деп аталады, ал барлық қабырғалары тамырға қарай бағытталған жағдайда, ол анти-арборесценция немесе кіру ағашы деп аталады. Тамырланған ағаштың өзін кейбір авторлар бағытталған график ретінде анықтаған. Тамырланған орман – тамырланған ағаштардың бірікпеген жиыны. Тамырланған орман бағытталған, бағытталған тамырланған орман деп аталуы мүмкін, оның барлық қабырғалары әр тамырланған ағашта тамырдан алыс бағытталған жағдайда, ол тармақталған немесе шығу орман деп аталады, ал барлық қабырғалары әр тамырланған ағашта тамырға қарай бағытталған жағдайда, ол анти-тармақталған немесе кіру орман деп аталады. Ағаш терминін 1857 жылы британдық математик Артур Кейли енгізген.

Орман

Орман – кез келген екі төбесі ең көп дегенде бір жолмен қосылған бағытталмаған граф. Басқаша айтқанда, орман – бағытталмаған циклсыз граф, оның барлық байланысқан компоненттері ағаштар болып табылады; яғни, граф ағаштардың жиынтық емес бірігімінен тұрады. Ерекше жағдайларда, нөлдік граф (нөл ағаштан тұратын орман), жалғыз ағаш және қабырғасыз граф – орманның мысалдары. Барлық ағаштар үшін 1 = V − E = 1 екендігін ескере отырып, орман ішіндегі ағаштар санын оңай есептеуге болады: барлық төбелер мен барлық қабырғалар арасындағы айырманы табу арқылы. 1 = V − E = орман ішіндегі ағаштар саны.

Политри

Көпағаш 2-ary ағаштар көбінесе екілік ағаштар деп аталады, ал 3-ary ағаштар кейде үштік ағаштар деп аталады.

Бұйрық берілген ағаш

Реттелген ағаш (сондай-ақ, жазық ағаш немесе орналасқан ағаш) – әрбір түйіннің балалары үшін белгілі бір ретпен орналастырылған тамырлы ағаш. Бұл "жазық ағаш" деп аталады, себебі балалардың реті ағашты жазықтықта бейнелеуге тең, онда түбір жоғарыда орналасқан, ал әрбір түйіннің балалары сол түйінден төмен орналасады. Егер жазықтықта тамырланған ағаштың бейнелеуі берілген болса, және балалардың бағытын, мысалы, солдан оңға қарай белгілесек, онда бейнелеу балалардың ретін анықтайды. Керісінше, егер реттелген ағаш берілген болса және түбірді дәстүрлі түрде жоғары орналастырсақ, онда реттелген ағаштағы бала түйіндерін солдан оңға қарай бейнелеу арқылы, жазықтықтағы дерлік бірегей бейнелеуге қол жеткізуге болады.

Қасиеттері

Әрбір ағаш екібөлікті график. График екібөлікті болып табылады, егер және тек қана онда тақ ұзындығы циклдер болмаса. Ағашта циклдер мүлдем болмағандықтан, ол екібөлікті болып табылады. Санаулы көп нүктесі бар әрбір ағаш – жазық график. Кез келген байланысты G графигі G-нің барлық нүктелерін қамтитын және қабырғалары G-нің қабырғалары болатын жайылма ағашты қабылдайды. Кез келген байланысты шекті графикте тереңдікке бірінші іздеу ағаштары және ендікке бірінші іздеу ағаштары сияқты нақты жайылма ағаш түрлері бар. Тереңдікке бірінші іздеу ағаштарының болуын жалпылап айтқанда, санаулы көп нүктесі бар кез келген байланысты графтың Тремо ағашы болады. Дегенмен, кейбір санаусыз ретті графиктерде мұндай ағаш жоқ. n > 1 нүктесі бар кез келген шекті ағашта кем дегенде екі терминалдық нүкте (жапырақтар) болады. Жапырақтардың бұл ең аз саны – жол графиктерге тән; ең көп саны, n − 1, тек жұлдыз тәрізді графиктерде ғана жетеді. Жапырақтардың саны ең үлкен нүкте дәрежесінен кем болмайды. Ағаштағы кез келген үш нүкте үшін олардың арасындағы үш жолдың бір ғана ортақ нүктесі болады. Жалпы алғанда, үш нүктенің арасындағы ең қысқа үш жолға жататын графиктегі нүкте осы нүктелердің медианасы деп аталады. Ағаштағы кез келген үш нүктенің бірегей медианасы болғандықтан, әрбір ағаш – медианалық график. Әрбір ағаштың ортасы бір немесе екі іргелес нүктеден тұрады. Ортасы – кез келген ең ұзын жолдың ортаңғы нүктесі немесе ортаңғы екі нүктесі. Сол сияқты, әрбір n нүктелі ағаштың центроиді бір немесе екі іргелес нүктеден тұрады. Бірінші жағдайда нүктені алып тастау ағашты n/2-ден аз нүктелі субағаштарға бөледі. Екінші жағдайда, екі центроидтық нүктелер арасындағы қабырғаны алып тастау ағашты дәл n/2 нүктелі екі субағашқа бөледі. Ағаштың ең үлкен кликалары оның қабырғаларымен сәйкес келеді, бұл ағаштар класының аз кликалары бар екенін білдіреді.

Белгіленген ағаштар

Кейли формуласы бойынша n белгіленген төбелері бар ағаштардың саны көрсетіледі. Классикалық дәлелдемеде Пруфер тізбектері қолданылады, олар күшті нәтижені табиғи түрде көрсетеді: 1, 2, ..., n төбелерінің сәйкесінше дәрежелері бар ағаштардың саны – бұл көпмүшелік коэффициент. Көбірек жалпы мәселе – бағытталмаған графтардағы жайылма ағаштарды санау, бұл матрицалық ағаш теоремасымен шешіледі. (Кейли формуласы – толық графтардағы жайылма ағаштардың ерекше жағдайы.) Кез келген мөлшердегі барлық кіші ағаштарды санаудың ұқсас мәселесі жалпы жағдайда #P толық болып табылады.

Ағаштар түрлері

Жол графигі (немесе сызықтық график) n төбеден тұрады, олар қатарластырылған, сондықтан i және i + 1 төбелері 1 = i = 1, …, n – 1 үшін бір қабырғамен байланысқан. Жұлдыз тәрізді ағаш – орталық төбеден, «түбір» деп аталатын, және оған қосылған бірнеше жол графиктерінен тұрады. Формальды түрде, ағаш егер дәл бір төбесінің дәрежесі 2-ден жоғары болса, онда ол жұлдыз тәрізді болады. Жұлдызды ағаш – бір ішкі төбеден (және n – 1 жапырақтан) тұратын ағаш. Басқаша айтқанда, n-ретті жұлдызды ағаш – мүмкіндігінше көп жапырақты n-ретті ағаш. Құрт ағашы – барлық төбелері орталық жолдың кіші графигінен 1 қашықтықта орналасқан ағаш. Лобстер ағашы – барлық төбелері орталық жолдың кіші графигінен 2 қашықтықта орналасқан ағаш. d дәрежелі тұрақты ағаш – әр төбесіне d қабырғасы бар шексіз ағаш. Олар еркін топтардың Кейли графиктері ретінде және Титс құрылыстарының теориясында пайда болады. Статистикалық механикада олар Бет торлары деп белгілі.