Кіріспе
Графтың жиектерін қанша орманға бөлуге болады
Бағытталмаған графтың ағаш саны – оның жиектерін бөлуге болатын орман санының ең төменгі мөлшері. Басқаша айтқанда, бұл графтың барлық жиектерін қамту үшін қажетті ең аз кеңейтілген орман саны. Нэш-Уильямс теоремасы графтың k-ағаш болуы үшін қажетті және жеткілікті шарттарды анықтайды.
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash Williams theorem provides necessary and sufficient conditions for when a graph is k arboric.
Мысал
Суретте толық екібөлікті K4,4 графигі көрсетілген, түстер оның қабырғаларының үш орманға бөлінгенін көрсетеді. K4,4 графигін одан аз орманға бөлу мүмкін емес, себебі оның сегіз төбесіндегі кез келген орманның ең көп дегені жеті қабырғасы болады, ал графиканың жалпы саны он алты қабырғаны құрайды, бұл бір орманның қабырғаларынан екі еседен астам. Сондықтан, K4,4 графигінің ағашқа тәндігі үшке тең.
Орманның тығыздығын өлшейтін өлшем
Графтың ағашқа ұқсастығы – графтың тығыздығын өлшеудің шамасы: көптеген қабырғалары бар графтардың ағашқа ұқсастығы жоғары, ал ағашқа ұқсастығы жоғары графтар тығыз кішіграфты қамтиды. Толығырақ айтқанда, кез келген n төбелі орманның ең көп дегенде n-1 қабырғасы болғандықтан, n төбесі және m қабырғасы бар графтың ағашқа ұқсастығы кем дегенде . Сонымен қатар, кез келген графтың кішіграфтары графтың өзінен жоғары ағашқа ұқсастыққа ие бола алмайды, немесе балама түрде графтың ағашқа ұқсастығы оның кез келген кішіграфтарының ең жоғары ағашқа ұқсастығынан кем болмауы керек. Нэш Уильямс осы екі фактіні ағашқа ұқсастықты сипаттау үшін біріктіруге болатынын дәлелдеді: егер біз nS және mS белгілемесі арқылы берілген графтың кез келген S кішіграфының төбелері мен қабырғаларының санын білдірсек, онда графтың ағашқа ұқсастығы тең .
Кез келген жазық графтың төбесіне ең көп қабырғасы болады, содан Нэш Уильямс формуласы бойынша жазық графтардың ағашқа ұқсастығы ең көп үшке тең. Шнайдер жазық графты кішкентай аумақты торға түсіру үшін, үш орманнан тұратын Шнайдер ағашы деп аталатын жазық графтың ерекше бөлінісін қолданды.
Алгоритмдер
Графтың ағашқа ұқсастығын матроидты бөлудің жалпы проблемасының ерекше жағдайы ретінде қарастыруға болады, онда матроид элементтерінің жиыны шектеулі тәуелсіз жиындардың бірігімі түрінде беріледі. Осының салдарынан, ағашқа ұқсастықты полиномиалдық уақыт алгоритмімен есептеу мүмкін. Қазіргі ең жақсы нақты алгоритм ағашқа ұқсастықты уақытта есептейді, мұнда – графтың қабырғаларының саны. Графтың ағашқа ұқсастығына жуықтап бағалауды одан да жылдам есептеуге болады. Сызықтық уақытта жұмыс істейтін 2-ге жуықтап бағалау алгоритмдері және 2-нің қосымша қатесі бар дерлік сызықтық уақыт алгоритмі бар.
Қарым-қатынас ұғымдары
Графтың анарбориктігі – графтың қабырғаларын жиексіз циклдық емес кішіграфтарға бөлуге болатын ең көп саны. Графтың жұлдыз тәрізді ағаш саны – графтың қабырғаларын бөлуге болатын ең кішкентай орманның мөлшері, оның әр ағашы жұлдыз (бір ғана жапырақ емес түйіні бар ағаш),. Егер ағаш өзі жұлдыз болмаса, оның жұлдыз тәрізді ағаш саны екіге тең, өйткені оның қабырғаларын ағаш түбірінен жұп және тақ қашықтықтағы екі жиынтыққа бөлуге болады. Сондықтан, кез келген графтың жұлдыз тәрізді ағаш саны кемінде ағаш санына тең, ал ең көп дегенде ағаш санының екі есесіне тең. Графтың сызықтық ағаш саны – графтың қабырғаларын бөлуге болатын сызықтық ормандардың (жолдар жиынтығы) ең кішкентай саны. Графтың сызықтық ағаш саны оның ең жоғары дәрежесімен және еңіс санымен тығыз байланысты. Графтың псевдоағаш саны – оның қабырғаларын бөлуге болатын псевдоормандардың ең кішкентай саны. Бұл графтың кез келген кішіграфындағы қабырғалар мен түйіндердің қатынасының ең жоғарғы мәні, толық санға дейін дөңгеленген. Ағаш саны сияқты, псевдоағаш саны да матроидтық құрылымға ие, бұл оны тиімді есептеуге мүмкіндік береді. Графтың кішіграф тығыздығы – оның ең тығыз кішіграфының тығыздығы. Графтың қалыңдығы – оның қабырғаларын бөлуге болатын жазық кішіграфтардың ең кішкентай саны. Кез келген жазық графтың ағаш саны үш болғандықтан, кез келген графтың қалыңдығы кемінде ағаш санының үштен біріне тең және ең көп дегенде ағаш санына тең. Графтың дегенерациясы – графтың барлық туындаған кішіграфтары бойынша кішіграфтағы түйіннің ең төменгі дәрежесінің ең жоғарғы мәні. Ағаш саны бар графтың дегенерациясы кемінде , ең көп дегенде , графтың түс саны, сондай-ақ оның Секерес-Вилф саны дегенерациясына 1-ді қосумен тең. Графтың күші – бөлшектік мән, оның толық бөлігі графқа сыйымды ең көп санды спан ағаштарының санын көрсетеді. Бұл ағаштарды қаптау мәселесіне қатысты, ағаш санымен туындаған жабу мәселесіне қарама-қарсы. Бұл екі параметрді Тютте және Нэш Уильямс бірге зерттеді. Бөлшек ағаш саны ағаш санын жетілдіреді, өйткені ол граф үшін былай анықталады: Басқаша айтқанда, графтың ағаш саны бөлшек ағаш санының толық бөлігіне тең. (a,b) ыдырау қабілеті ағаш санын жалпылайды. Егер графтың қабырғалары жиынтықтарға бөлінсе, онда ол ыдырайды, олардың әрқайсысы орманды тудырады, ең жоғары дәрежесі бар графты тудыратынды қоспағанда. Ағаш саны бар граф ыдырайды. Ағаш саны – графтың қабырғаларын жабатын ең кішкентай ағаштар саны.
The subgraph density of a graph is the density of its densest subgraph. The thickness of a graph is the minimum number of planar subgraphs into which its edges can be partitioned. As any planar graph has arboricity three, the thickness of any graph is at least equal to a third of the arboricity, and at most equal to the arboricity. The degeneracy of a graph is the maximum, over all induced subgraphs of the graph, of the minimum degree of a vertex in the subgraph. The degeneracy of a graph with arboricity is at least equal to , and at most equal to The coloring number of a graph, also known as its Szekeres Wilf number is always equal to its degeneracy plus 1
The strength of a graph is a fractional value whose integer part gives the maximum number of disjoint spanning trees that can be drawn in a graph. It is the packing problem that is dual to the covering problem raised by the arboricity. The two parameters have been studied together by Tutte and Nash Williams. The fractional arboricity is a refinement of the arboricity, as it is defined for a graph as In other terms, the arboricity of a graph is the ceiling of the fractional arboricity. The (a,b) decomposability generalizes the arboricity. A graph is decomposable if its edges can be partitioned into sets, each one of them inducing a forest, except one who induces a graph with maximum degree A graph with arboricity is decomposable. The tree number is the minimal number of trees covering the edges of a graph.
Арнайы кездесулер
Ағаштық Голдберг-Сеймур болжамында кездеседі.