Treewidth
આલેખ સિદ્ધાંતમાં, દિશાહીન આલેખની ત્રિ-પહોળાઈ એ એક પૂર્ણાંક સંખ્યા છે જે અનૌપચારિક રીતે, આલેખ વૃક્ષથી કેટલો દૂર છે તે સ્પષ્ટ કરે છે. સૌથી નાની ત્રિ-પહોળાઈ 1 છે; ત્રિ-પહોળાઈ 1 વાળા આલેખ બરાબર વૃક્ષો અને જંગલો છે. મહત્તમ 2 ત્રિ-પહોળાઈ ધરાવતા આલેખ શ્રેણી-સમાંતર આલેખ છે. બરાબર ત્રિ-પહોળાઈવાળા મહત્તમ આલેખને-વૃક્ષો કહેવામાં આવે છે, અને મહત્તમ ત્રિ-પહોળાઈવાળા આલેખને આંશિક-વૃક્ષો કહેવામાં આવે છે. અન્ય ઘણા સારી રીતે અભ્યાસ કરાયેલા આલેખ પરિવારો પણ ત્રણ પહોળાઈથી બંધાયેલા છે. ત્રિ-પહોળાઈને ઔપચારિક રીતે ઘણી સમકક્ષ રીતોથી વ્યાખ્યાયિત કરી શકાય છેઃ આલેખના વૃક્ષના વિઘટનમાં સૌથી મોટા શિરોબિંદુ સમૂહના કદની દ્રષ્ટિએ, આલેખની કોર્ડલ પૂર્ણતામાં સૌથી મોટા જૂથના કદની દ્રષ્ટિએ, આલેખ પર પીછો-ચોરીની રમત માટેની વ્યૂહરચનાનું વર્ણન કરતા આશ્રયસ્થાનના મહત્તમ ક્રમની દ્રષ્ટિએ, અથવા કાંટાદારના મહત્તમ ક્રમની દ્રષ્ટિએ, જોડાયેલા સબગ્રાફ્સનો સંગ્રહ કે જે બધા એકબીજાને સ્પર્શ કરે છે. ત્રણ પહોળાઈનો ઉપયોગ સામાન્ય રીતે ગ્રાફ અલ્ગોરિધમ્સના પરિમાણિત જટિલતા વિશ્લેષણમાં પરિમાણ તરીકે થાય છે. ઘણા અલ્ગોરિધમ્સ કે જે સામાન્ય આલેખ માટે એન. પી.-સખત હોય છે, જ્યારે ત્રણ પહોળાઈ અચળાંક દ્વારા બંધાયેલ હોય ત્યારે સરળ બને છે. ત્રિ-પહોળાઈનો ખ્યાલ મૂળરૂપે પરિમાણના નામ હેઠળ રજૂ કરવામાં આવ્યો હતો. પાછળથી તેને અલગ ગ્રાફ પરિમાણ, હેડવિગર નંબર સાથે વહેંચાયેલા ગુણધર્મોના આધારે ફરીથી શોધવામાં આવ્યું હતું. પાછળથી તેને અન્ય ઘણા લેખકો દ્વારા ફરીથી શોધવામાં આવી હતી અને ત્યારથી તેનો અભ્યાસ કરવામાં આવ્યો છે. વ્યાખ્યા ગ્રાફનું વૃક્ષનું વિઘટન એ નોડ્સ સાથેનું વૃક્ષ છે, જ્યાં દરેક નોડ્સનો સબસેટ છે, જે નીચેના ગુણધર્મોને સંતોષે છે (નોડ શબ્દનો ઉપયોગ શિરોબિંદુઓ સાથે મૂંઝવણ ટાળવા માટે નોડ્સના શિરોબિંદુને સંદર્ભિત કરવા માટે થાય છે): બધા સમૂહોનું જોડાણ સમાન હોય છે. એટલે કે, દરેક આલેખ શિરોબિંદુ ઓછામાં ઓછા એક વૃક્ષ નોડમાં સમાયેલ છે. જો અને બંનેમાં શિરોબિંદુ હોય, તો પછી વચ્ચેના (અનન્ય) માર્ગના તમામ ગાંઠો અને તેમાં પણ હોય છે. તેવી જ રીતે, શિરોબિંદુ ધરાવતા વૃક્ષના ગાંઠો એક જોડાયેલ ઉપવૃક્ષા બનાવે છે. આલેખમાં દરેક ધાર માટે, એક સબસેટ છે જેમાં અને બંનેનો સમાવેશ થાય છે. એટલે કે, શિરોબિંદુઓ ગ્રાફમાં ત્યારે જ અડીને હોય છે જ્યારે અનુરૂપ સબટ્રીમાં નોડ સામાન્ય હોય. વૃક્ષના વિઘટનની પહોળાઈ એ તેના સૌથી મોટા સમૂહ બાદબાકી એકનું કદ છે. આલેખની ત્રિ-પહોળાઈ એ વૃક્ષના તમામ સંભવિત વિઘટનમાં લઘુતમ પહોળાઈ છે. આ વ્યાખ્યામાં, વૃક્ષની ત્રણ પહોળાઈને એકની બરાબર બનાવવા માટે સૌથી મોટા સમૂહનું કદ એક દ્વારા ઘટાડવામાં આવે છે. સમાનરૂપે, ની ત્રિ-પહોળાઈ સૌથી નાના જૂથ નંબર સાથે કોર્ડલ ગ્રાફમાં સૌથી મોટા જૂથના કદ કરતાં એક ઓછી છે. દરેક બે શિરોબિંદુઓ વચ્ચેની ધારમાં ઉમેરીને આ જૂથનું કદ ધરાવતો કોર્ડલ ગ્રાફ મેળવી શકાય છે, જે બંને ઓછામાં ઓછા એક સમૂહ સાથે સંબંધિત છે. ત્રણ પહોળાઈને આશ્રયસ્થાનોની દ્રષ્ટિએ પણ વર્ગીકૃત કરી શકાય છે, જે આલેખ પર વ્યાખ્યાયિત ચોક્કસ પીછો-કરચોરીની રમત માટે કરચોરીની વ્યૂહરચનાનું વર્ણન કરે છે. ગ્રાફમાં ત્રણ પહોળાઈ હોય છે જો અને માત્ર ત્યારે જ જો તેમાં હેવન ઓફ ઓર્ડર હોય પરંતુ કોઈ ઉચ્ચ ક્રમ ન હોય, જ્યાં હેવન ઓફ ઓર્ડર એ એક કાર્ય છે જે મોટાભાગના શિરોબિંદુઓના દરેક સમૂહને જોડાયેલા ઘટકોમાંના એકમાં મેપ કરે છે અને જે એકવિધતાના ગુણધર્મનું પાલન કરે છે. સમાન લાક્ષણિકતા કાંટાનો ઉપયોગ કરીને પણ કરી શકાય છે, જોડાયેલા સબગ્રાફ્સના પરિવારો કે જે બધા એકબીજાને સ્પર્શ કરે છે (જેનો અર્થ છે કે તેઓ શિરોબિંદુ વહેંચે છે અથવા ધાર દ્વારા જોડાયેલા છે). બ્રેમ્બલનો ક્રમ એ સબગ્રાફ્સના પરિવાર માટે સૌથી નાનો હિટ સેટ છે, અને ગ્રાફની ત્રિ-પહોળાઈ બ્રેમ્બલના મહત્તમ ક્રમ કરતાં એક ઓછી છે. ઉદાહરણો દરેક સંપૂર્ણ આલેખમાં ત્રિ-પહોળાઈ હોય છે. કોર્ડલ આલેખની દ્રષ્ટિએ ત્રિ-પહોળાઈની વ્યાખ્યાનો ઉપયોગ કરીને આ સૌથી સરળતાથી જોવામાં આવે છેઃ સંપૂર્ણ આલેખ પહેલેથી જ કોર્ડલ છે, અને વધુ ધાર ઉમેરવાથી તેના સૌથી મોટા જૂથના કદમાં ઘટાડો થઈ શકતો નથી. ઓછામાં ઓછા બે શિરોબિંદુઓ સાથે જોડાયેલા આલેખમાં ત્રણ પહોળાઈ 1 હોય છે જો અને માત્ર જો તે વૃક્ષ હોય. એક વૃક્ષની ત્રણ પહોળાઈ હોય છે જે સંપૂર્ણ આલેખ માટે સમાન તર્ક દ્વારા હોય છે (એટલે કે, તે કોર્ડલ હોય છે, અને મહત્તમ જૂથનું કદ બે હોય છે). તેનાથી વિપરીત, જો આલેખમાં એક ચક્ર હોય, તો આલેખની દરેક કોર્ડલ પૂર્ણતામાં ચક્રના સતત ત્રણ શિરોબિંદુઓ ધરાવતો ઓછામાં ઓછો એક ત્રિકોણ હોય છે, જેમાંથી તે અનુસરે છે કે તેની ત્રિ-પહોળાઈ ઓછામાં ઓછી બે છે. બાઉન્ડેડ ત્રિ-પહોળાઈ સાથે બાઉન્ડેડ ત્રિ-પહોળાઈ આલેખ પરિવારો કોઈપણ નિશ્ચિત અચળાંક માટે, ત્રિ-પહોળાઈના આલેખને મહત્તમ આંશિક-વૃક્ષો કહેવામાં આવે છે. બંધાયેલ ત્રિ-પહોળાઈવાળા આલેખના અન્ય પરિવારોમાં કેક્ટસ આલેખ, સ્યુડોફોરેસ્ટ, શ્રેણી-સમાંતર આલેખ, બાહ્ય સમતલ આલેખ, હેલિન આલેખ અને એપોલોનિયન નેટવર્કનો સમાવેશ થાય છે. સંરચિત કાર્યક્રમોના સંકલનમાં ઉદ્ભવતા નિયંત્રણ-પ્રવાહ આલેખમાં ત્રણ પહોળાઈ પણ મર્યાદિત હોય છે, જે રજિસ્ટર ફાળવણી જેવા ચોક્કસ કાર્યોને તેમના પર અસરકારક રીતે કરવાની મંજૂરી આપે છે. સમતલીય આલેખમાં ત્રિ-પહોળાઈ બંધાયેલ નથી, કારણ કે ગ્રીડ આલેખ બરાબર ત્રિ-પહોળાઈ ધરાવતો સમતલીય આલેખ છે. તેથી, જો મર્યાદિત ત્રિ-પહોળાઈ ધરાવતો લઘુ-બંધ આલેખ પરિવાર હોય, તો તેમાં તમામ સમતલીય આલેખનો સમાવેશ થઈ શકતો નથી. તેનાથી વિપરીત, જો કેટલાક સમતલીય આલેખ કુટુંબમાં આલેખ માટે નાના તરીકે ન આવી શકે, તો ત્યાં એક સ્થિરાંક છે કે જેમાં તમામ આલેખ મહત્તમ ત્રણ પહોળાઈ ધરાવે છે. એટલે કે, નીચેની ત્રણ શરતો એકબીજાની સમકક્ષ છેઃ બંધાયેલ-ત્રિ-પહોળાઈ આલેખનો એક નાનો બંધ પરિવાર છે; મર્યાદિત રીતે પ્રતિબંધિત ઘણા નાનાઓમાંથી એક સમતલીય છે; એક નાનો બંધ આલેખ પરિવાર છે જેમાં તમામ સમતલીય આલેખનો સમાવેશ થતો નથી. દરેક મર્યાદિત મૂલ્ય માટે, મહત્તમ ત્રિ-પહોળાઈના આલેખ પ્રતિબંધિત સગીરના મર્યાદિત સમૂહ દ્વારા વર્ગીકૃત થઈ શકે છે. (એટલે કે, ત્રિ-પહોળાઈના કોઈપણ આલેખમાં નાના તરીકે સમૂહમાં એક આલેખનો સમાવેશ થાય છે.) પ્રતિબંધિત સગીરના આ દરેક સમૂહમાં ઓછામાં ઓછો એક સમતલ આલેખનો સમાવેશ થાય છે. કારણ કે, અનન્ય પ્રતિબંધિત ગૌણ એ 3-વર્ટેક્સ ચક્ર આલેખ છે. કારણ કે, અનન્ય પ્રતિબંધિત ગૌણ એ 4-વર્ટેક્સ સંપૂર્ણ આલેખ છે. કારણ કે, ચાર પ્રતિબંધિત ગૌણ છેઃ, અષ્ટકોણનો આલેખ, પંચકોણીય પ્રિઝમ આલેખ અને વેગનર આલેખ. આમાંથી, બે પોલિહેડ્રલ આલેખ સમતલીય છે. ના મોટા મૂલ્યો માટે, પ્રતિબંધિત સગીરની સંખ્યા ઓછામાં ઓછી તેટલી ઝડપથી વધે છે જેટલી ઝડપથી ના વર્ગમૂળના ઘાતાંકીય. જો કે, પ્રતિબંધિત સગીરના કદ અને સંખ્યા પરની જાણીતી ઉપલી સીમાઓ આ નીચલી સીમા કરતાં ઘણી વધારે છે. એલ્ગોરિધમ્સ ત્રિ-પહોળાઈની ગણતરી આપેલ આલેખમાં આપેલ ચલની મહત્તમ ત્રિ-પહોળાઈ છે કે કેમ તે નક્કી કરવા માટે તે એન. પી.-પૂર્ણ છે. જો કે, જ્યારે કોઈ નિશ્ચિત અચળાંક હોય, ત્યારે ત્રિ-પહોળાઈવાળા આલેખ ઓળખી શકાય છે, અને તેમના માટે એક પહોળાઈ વૃક્ષનું વિઘટન, રેખીય સમયમાં બનાવવામાં આવે છે. આ અલ્ગોરિધમનો સમય અવલંબન ઘાતાંકીય છે. વિશાળ સંખ્યામાં ક્ષેત્રોમાં ત્રિ-પહોળાઈની ભૂમિકાઓને કારણે, આલેખની ત્રિ-પહોળાઈની ગણતરી કરતા વિવિધ વ્યવહારુ અને સૈદ્ધાંતિક અલ્ગોરિધમ્સ વિકસાવવામાં આવ્યા હતા. હાથ પરની એપ્લિકેશનના આધારે, કોઈ વધુ સારો અંદાજ ગુણોત્તર પસંદ કરી શકે છે, અથવા ઇનપુટના કદ અથવા ત્રણ પહોળાઈથી ચાલતા સમયમાં વધુ સારી અવલંબન પસંદ કરી શકે છે. નીચેનું કોષ્ટક કેટલાક ત્રિ-પહોળાઈ અલ્ગોરિધમ્સની ઝાંખી આપે છે. અહીં ત્રિ-પહોળાઈ છે અને તે ઇનપુટ ગ્રાફના શિરોબિંદુઓની સંખ્યા છે. દરેક અલ્ગોરિધમ્સ સમય જતાં એપ્રોક્સીમેશન કોલમમાં આપવામાં આવેલી પહોળાઈનું વિઘટન કરે છે. ઉદાહરણ તરીકે, સમયનો અલ્ગોરિધમ કાં તો મહત્તમ પહોળાઈના ઇનપુટ ગ્રાફના વૃક્ષ વિઘટનનું નિર્માણ કરે છે અથવા અહેવાલ આપે છે કે તેની ત્રિ-પહોળાઈ તેના કરતા વધારે છે. તેવી જ રીતે, સમયનો અલ્ગોરિધમ કાં તો મહત્તમ પહોળાઈના ઇનપુટ ગ્રાફના વૃક્ષ વિઘટનનું નિર્માણ કરે છે અથવા અહેવાલ આપે છે કે તેની ત્રિ-પહોળાઈ તેના કરતા વધારે છે. તે જ ચાલી રહેલા સમયમાં તેમાં સુધારો કર્યો. તે જાણીતું નથી કે સમતલ આલેખની ત્રિ-પહોળાઈ નક્કી કરવી એ એન. પી.-પૂર્ણ છે કે નહીં, અથવા તેમની ત્રિ-પહોળાઈની ગણતરી બહુપદી સમયમાં કરી શકાય છે કે કેમ. વ્યવહારમાં, એક અલ્ગોરિધમ 100 શિરોબિંદુઓ સુધીના આલેખની ત્રિ-પહોળાઈ અને 11 સુધી ત્રિ-પહોળાઈ નક્કી કરી શકે છે, જેમાં શ્રેષ્ઠ ત્રિ-પહોળાઈ સાથે આ આલેખની કોર્ડલ પૂર્ણતા શોધી શકાય છે. મોટા આલેખ માટે, ત્રિ-પહોળાઈની ગણતરી કરવા માટે શાખા અને બંધાયેલ શોધ (બીએનબી) અને શ્રેષ્ઠ-પ્રથમ શોધ જેવી શોધ-આધારિત તકનીકોનો ઉપયોગ કરી શકાય છે. આ અલ્ગોરિધમ્સ કોઈપણ સમયે હોય છે જેમાં જ્યારે વહેલા બંધ કરવામાં આવે છે, ત્યારે તેઓ ત્રિ-પહોળાઈ પર ઉપલા બાઉન્ડનું આઉટપુટ આપશે. ત્રણ પહોળાઈની ગણતરી માટે પ્રથમ બીએનબી અલ્ગોરિધમ, જેને ક્વિકબીબી અલ્ગોરિધમ કહેવાય છે, તે ગોગેટ અને ડેક્ટર દ્વારા પ્રસ્તાવિત કરવામાં આવ્યું હતું. કોઈપણ બી. એન. બી. અલ્ગોરિધમની ગુણવત્તા ઉપયોગમાં લેવાતી નીચલી બાઉન્ડની ગુણવત્તા પર ખૂબ જ નિર્ભર હોવાથી, ગોગેટ અને ડેક્ટરે નાની-ઓછી-પહોળાઈ તરીકે ઓળખાતી ત્રિ-પહોળાઈ પર નીચલી-બાઉન્ડની ગણતરી કરવા માટે એક નવીન અલ્ગોરિધમનો પણ પ્રસ્તાવ મૂક્યો હતો. ઉચ્ચ સ્તરે, લઘુતમ-લઘુતમ-પહોળાઈ એલ્ગોરિધમ એ હકીકતોને જોડે છે કે આલેખની ત્રિ-પહોળાઈ ક્યારેય તેની લઘુતમ ડિગ્રી કરતાં મોટી હોતી નથી અથવા ત્રિ-પહોળાઈ પર નીચી સીમા મેળવવા માટે તેની લઘુતમ હોય છે. લઘુતમ-લઘુતમ-પહોળાઈ એલ્ગોરિધમ વારંવાર લઘુતમ ડિગ્રી શિરોબિંદુ અને તેના પડોશીઓમાંથી એક વચ્ચેની ધારને સંકોચાઈને લઘુ આલેખ બનાવે છે, જ્યાં સુધી માત્ર એક શિરોબિંદુ રહે નહીં. આ બિલ્ટ માઇનર્સ પર મહત્તમ લઘુત્તમ ડિગ્રી ગ્રાફની ત્રિ-પહોળાઈ પર નીચલી બાઉન્ડ હોવાની ખાતરી આપવામાં આવે છે. ડાઉ અને કોર્ફે શ્રેષ્ઠ-પ્રથમ શોધનો ઉપયોગ કરીને ક્વિકબીબી અલ્ગોરિધમમાં સુધારો કર્યો. ચોક્કસ આલેખ પર, આ શ્રેષ્ઠ-પ્રથમ શોધ અલ્ગોરિધમ ક્વિકબીબી કરતા વધુ ઝડપી તીવ્રતાનો ક્રમ છે. નાના ત્રિ-પહોળાઈના આલેખ પર અન્ય સમસ્યાઓનું સમાધાન 1970ના દાયકાની શરૂઆતમાં, એવું જોવા મળ્યું હતું કે આલેખ પર વ્યાખ્યાયિત સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓનો મોટો વર્ગ બિન-ક્રમિક ગતિશીલ પ્રોગ્રામિંગ દ્વારા અસરકારક રીતે ઉકેલી શકાય છે, જ્યાં સુધી આલેખમાં બંધાયેલ પરિમાણ હોય, જે ત્રિ-પહોળાઈની સમકક્ષ હોવાનું દર્શાવતું પરિમાણ હોય. પાછળથી, કેટલાક લેખકોએ 1980 ના દાયકાના અંતમાં સ્વતંત્ર રીતે અવલોકન કર્યું હતું કે મનસ્વી આલેખ માટે એન. પી.-પૂર્ણ હોય તેવી ઘણી અલ્ગોરિધમિક સમસ્યાઓ આ આલેખના વૃક્ષ-વિઘટનનો ઉપયોગ કરીને બંધાયેલા ત્રિ-પહોળાઈના આલેખ માટે ગતિશીલ પ્રોગ્રામિંગ દ્વારા અસરકારક રીતે ઉકેલી શકાય છે. ઉદાહરણ તરીકે, ત્રિ-પહોળાઈના આલેખને રંગવાની સમસ્યાને આલેખના વૃક્ષ વિઘટન પર ગતિશીલ પ્રોગ્રામિંગ અલ્ગોરિધમનો ઉપયોગ કરીને ઉકેલી શકાય છે. વૃક્ષના વિઘટનના દરેક સમૂહ માટે, અને રંગ વર્ગોમાં શિરોબિંદુઓના દરેક વિભાજન માટે, અલ્ગોરિધમ નક્કી કરે છે કે તે રંગ માન્ય છે કે કેમ અને વૃક્ષના વિઘટનમાં તમામ વંશજ ગાંઠો સુધી વિસ્તૃત કરી શકાય છે, તે ગાંઠો પર ગણતરી અને સંગ્રહિત સમાન પ્રકારની માહિતીને જોડીને. પરિણામી અલ્ગોરિધમ સમયસર-વર્ટેક્સ ગ્રાફનો શ્રેષ્ઠ રંગ શોધે છે, જે સમયબદ્ધ છે જે આ સમસ્યાને નિશ્ચિત-પરિમાણને ઉકેલવા યોગ્ય બનાવે છે. કોર્સેલનો પ્રમેય સમસ્યાઓના મોટા વર્ગ માટે, વર્ગમાંથી સમસ્યાને ઉકેલવા માટે એક રેખીય સમય અલ્ગોરિધમ છે જો સતત બંધાયેલ ત્રિ-પહોળાઈ સાથે વૃક્ષ-વિઘટન પ્રદાન કરવામાં આવે. ખાસ કરીને, કોર્સેલનો પ્રમેય જણાવે છે કે જો ગ્રાફની સમસ્યાને મોનડિક સેકન્ડ ઓર્ડર લોજિકનો ઉપયોગ કરીને ગ્રાફના તર્કમાં વ્યક્ત કરી શકાય, તો તેને બાઉન્ડેડ ટ્રીવિડ્થવાળા ગ્રાફ પર રેખીય સમયમાં ઉકેલી શકાય છે. મોનડિક સેકન્ડ ઓર્ડર લોજિક એ આલેખના ગુણધર્મોને વર્ણવવા માટેની ભાષા છે જે નીચેની રચનાઓનો ઉપયોગ કરે છેઃ લોજિક ઓપરેશન્સ, જેમ કે સભ્યપદ પરીક્ષણો, જેમ કે, શિરોબિંદુઓ, ધાર, શિરોબિંદુઓના સમૂહો અને/અથવા ધારોના સમૂહો, જેમ કે,,, એડજેન્સી પરીક્ષણો (એક અંતિમ બિંદુ છે), અને કેટલાક એક્સ્ટેન્શન્સ કે જે ઓપ્ટિમાઇઝેશન જેવી વસ્તુઓને મંજૂરી આપે છે. ઉદાહરણ તરીકે આલેખ માટે 3-રંગની સમસ્યાનો વિચાર કરો. આલેખ માટે, આ સમસ્યા પૂછે છે કે શું દરેક શિરોબિંદુને 3 રંગોમાંથી એક એ રીતે સોંપવું શક્ય છે કે જેથી કોઈ પણ બે અડીને આવેલા શિરોબિંદુઓને સમાન રંગ સોંપવામાં ન આવે. આ સમસ્યાને મોનડિક સેકન્ડ ઓર્ડર તર્કમાં નીચે પ્રમાણે વ્યક્ત કરી શકાય છેઃ, જ્યાં, 3 રંગોમાંથી દરેક ધરાવતા શિરોબિંદુઓના ઉપગણોનું પ્રતિનિધિત્વ કરે છે. તેથી, કોર્સેલના પરિણામો દ્વારા, 3-રંગની સમસ્યાને ગ્રાફ માટે રેખીય સમયમાં ઉકેલી શકાય છે, જેમાં બંધાયેલ અચળ ત્રિ-પહોળાઈનું વૃક્ષ-વિઘટન આપવામાં આવે છે. સંબંધિત પરિમાણો પાથવિડ્થ ગ્રાફની પાથવિડ્થ વૃક્ષના વિઘટન દ્વારા ત્રણ પહોળાઈની ખૂબ જ સમાન વ્યાખ્યા ધરાવે છે, પરંતુ તે વૃક્ષના વિઘટન સુધી મર્યાદિત છે જેમાં વિઘટનનું અંતર્ગત વૃક્ષ પાથ ગ્રાફ છે. વૈકલ્પિક રીતે, પાથવિડ્થને અંતરાલ આલેખમાંથી સમાનરૂપે કોર્ડલ આલેખમાંથી ત્રિ-પહોળાઈની વ્યાખ્યા સાથે વ્યાખ્યાયિત કરી શકાય છે. પરિણામે, આલેખની પાથવિડ્થ હંમેશા તેની ત્રણ પહોળાઈ જેટલી મોટી હોય છે, પરંતુ તે માત્ર લઘુગણક પરિબળ દ્વારા મોટી થઈ શકે છે. અન્ય પરિમાણ, ગ્રાફ બેન્ડવિડ્થ, યોગ્ય અંતરાલ આલેખમાંથી સમાન વ્યાખ્યા ધરાવે છે, અને ઓછામાં ઓછું પાથવિડ્થ જેટલું મોટું છે. અન્ય સંબંધિત પરિમાણોમાં વૃક્ષ-ઊંડાઈનો સમાવેશ થાય છે, એક સંખ્યા જે નાના-બંધ આલેખ પરિવાર માટે બંધાયેલ હોય છે જો અને માત્ર ત્યારે જ જો કુટુંબ કોઈ માર્ગને બાકાત રાખે, અને અધોગતિ, ગ્રાફની અંતરનું માપ જે તેની ત્રિ-પહોળાઈ જેટલું હોય. ગ્રીડનું નાનું કદ કારણ કે ગ્રીડ ગ્રાફની ત્રિ-પહોળાઈ છે, ગ્રાફની ત્રિ-પહોળાઈ હંમેશા સૌથી મોટા ચોરસ ગ્રીડના કદ કરતા વધારે અથવા તેની બરાબર હોય છે. બીજી દિશામાં, રોબર્ટસન અને સીમોર દ્વારા ગ્રીડ માઇનોર થીયરમ દર્શાવે છે કે ત્યાં એક અમર્યાદિત કાર્ય અસ્તિત્વમાં છે જેમ કે સૌથી મોટી ચોરસ ગ્રીડ માઇનોરનું કદ ઓછામાં ઓછું ત્રણ પહોળાઈ હોય છે. જાણીતી શ્રેષ્ઠ સીમાઓ એ છે કે ઓછામાં ઓછા અમુક નિશ્ચિત અચળાંક માટે હોવી જોઈએ, અને વધુમાં વધુ નીચલા બાઉન્ડમાં નોટેશન માટે, મોટા O નોટેશન જુઓ. સખત સીમાઓ પ્રતિબંધિત ગ્રાફ પરિવારો માટે જાણીતી છે, જે દ્વિ-પરિમાણીયતાના સિદ્ધાંત દ્વારા તે પરિવારો પર ઘણી ગ્રાફ ઓપ્ટિમાઇઝેશન સમસ્યાઓ માટે કાર્યક્ષમ અલ્ગોરિધમ્સ તરફ દોરી જાય છે. હેલિનનું ગ્રીડ પ્રમેય અનંત આલેખ માટે ત્રિ-પહોળાઈ અને ગ્રીડ નાના કદ વચ્ચેના સંબંધનું એનાલોગ પ્રદાન કરે છે. વ્યાસ અને સ્થાનિક ત્રિ-પહોળાઈ સબગ્રાફ લેવા હેઠળ બંધ કરાયેલા આલેખનો એક પરિવાર સ્થાનિક ત્રિ-પહોળાઈ અથવા વ્યાસ-ત્રિ-પહોળાઈના ગુણધર્મને બંધાયેલો હોવાનું કહેવાય છે, જો પરિવારમાં આલેખોની ત્રિ-પહોળાઈ તેમના વ્યાસના કાર્ય દ્વારા ઉપરની બાજુએ બંધાયેલ હોય. જો વર્ગ પણ સગીરને લેવા હેઠળ બંધ હોવાનું માનવામાં આવે છે, તો પછી સ્થાનિક ત્રિ-પહોળાઈને બંધ કરવામાં આવે છે જો અને માત્ર ત્યારે જ જો પ્રતિબંધિત સગીરમાંથી એક માટે ટોચનો આલેખ હોય. આ પરિણામના મૂળ પુરાવાઓ દર્શાવે છે કે ટોચના-નાના-મુક્ત આલેખ પરિવારમાં ત્રિ-પહોળાઈ વ્યાસના કાર્ય તરીકે સૌથી વધુ બમણી ઝડપથી વધે છે; પાછળથી આ એકલી ઘાતાંકીય અને અંતે રેખીય બાઉન્ડમાં ઘટાડવામાં આવી હતી. બાઉન્ડેડ લોકલ ટ્રીવિડ્થ દ્વિ-પરિમાણીયતાના અલ્ગોરિધમિક સિદ્ધાંત સાથે નજીકથી સંબંધિત છે, અને પ્રથમ ક્રમના તર્કમાં વ્યાખ્યાયિત કરી શકાય તેવા દરેક ગ્રાફ ગુણધર્મને ટોચના-નાના-મુક્ત ગ્રાફ પરિવાર માટે માત્ર થોડો જ સુપરલિનીયર સમયગાળામાં નક્કી કરી શકાય છે. તે આલેખના વર્ગ માટે પણ શક્ય છે કે જે સગીર હેઠળ બંધ ન હોય, તે સ્થાનિક ત્રિ-પહોળાઈથી બંધાયેલ હોય. ખાસ કરીને આ બાઉન્ડેડ ડિગ્રી ગ્રાફના વર્ગ માટે તુચ્છ રીતે સાચું છે, કારણ કે બાઉન્ડેડ વ્યાસ સબગ્રાફ્સ બાઉન્ડેડ કદ ધરાવે છે. બીજું ઉદાહરણ 1-સમતલીય આલેખ દ્વારા આપવામાં આવે છે, આલેખ કે જે સમતલમાં એક ધાર દીઠ પાર સાથે દોરી શકાય છે, અને વધુ સામાન્ય રીતે આલેખ માટે કે જે બંધાયેલ જીનસની સપાટી પર દોરવામાં આવે છે જેમાં ધાર દીઠ બંધાયેલ સંખ્યામાં પાર હોય છે. બંધાયેલ સ્થાનિક ત્રિ-પહોળાઈના નાના બંધ આલેખ પરિવારોની જેમ, આ ગુણધર્મ આ આલેખ માટે કાર્યક્ષમ અંદાજ અલ્ગોરિધમ્સનો માર્ગ નિર્દેશ કરે છે. હેડવિગર નંબર અને એસ-ફંક્શન્સ ગ્રાફ પરિમાણોના વર્ગને વ્યાખ્યાયિત કરે છે જેને તેઓ-ફંક્શન્સ કહે છે, જેમાં ત્રિ-પહોળાઈનો સમાવેશ થાય છે. આલેખથી પૂર્ણાંકો સુધીના આ વિધેયો કોઈ ધાર વગરના આલેખ પર શૂન્ય હોવા જરૂરી છે, નાના-એકવિધ હોવા જરૂરી છે (એક વિધેયને "નાના-એકવિધ" તરીકે ઓળખવામાં આવે છે જો, જ્યારે પણ તે નાનું હોય, તો એક હોય છે), જ્યારે એક નવો શિરોબિંદુ ઉમેરવામાં આવે છે જે અગાઉના તમામ શિરોબિંદુઓને અડીને હોય, અને જૂથ વિભાજકની બંને બાજુના બે પેટા આલેખમાંથી મોટા મૂલ્ય લેવા માટે. આવા તમામ કાર્યોનો સમૂહ તત્વની દ્રષ્ટિએ લઘુતમ અને મહત્તમકરણની કામગીરી હેઠળ સંપૂર્ણ જાળી બનાવે છે. આ જાળીમાં ટોચનું તત્વ ત્રિ-પહોળાઈ છે, અને નીચેનું તત્વ હેડવિગર નંબર છે, જે આપેલ આલેખમાં સૌથી મોટા સંપૂર્ણ ગૌણનું કદ છે. નોંધો સંદર્ભો. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . આલેખ અપરિવર્તન આલેખ લઘુ સિદ્ધાંત