FA
All
Articles
Dictionary
Quotes
Map

Wikiwand ❤️ Wikipedia

PrivacyTerms

عرض درخت

From Wikipedia, the free encyclopedia

عرض درخت
تجزیه‌ی درختیتجزیه‌ی درختی نرممجموعه‌ی مستقل بر روی تجزیه‌ی درختیالگوریتم‌های محاسبهٔ عرض درختی یک گرافمسئله‌ی دزد و پلیس‌هامنابع

در نظریه گراف، عرض درختی یک گراف بدون جهت، عددی‌ است که مربوط به آن گراف است. این عدد می‌تواند به طرق مختلفی تعریف شود: اندازهٔ بزرگ‌ترین راس در تجریهٔ درختی آن گراف، اندازهٔ بزرگ‌ترین خوشه در تکمیل وتری و ... .مفهوم عرض درختی یک گراف، در ابتدا توسط Umberto Bertelé و Francesco Brioschi در سال ۱۹۷۲ معرفی شد. بعدها به‌صورت جدی توسط Neil Robertson و Paul Seymour در سال ۱۹۸۴ مجدداً معرفی گردید. برای تعریف عرض درختی یک گراف، ابتدا باید تجریهٔ درختی گراف را تعریف کنیم.

تجزیهٔ درختی گراف G = ( V , E ) {\displaystyle G=(V,E)} {\displaystyle G=(V,E)}، درختی‌ است مانند T {\displaystyle T} {\displaystyle T} با رئوس X 1 , X 2 , . . . , X n {\displaystyle X_{1},X_{2},...,X_{n}} {\displaystyle X_{1},X_{2},...,X_{n}} (به این رئوس کیف یا bag می‌گویند) که در آن هر X i {\displaystyle X_{i}} {\displaystyle X_{i}} یک زیرمجموعه‌ای از V {\displaystyle V} {\displaystyle V} است که شرایط زیر را ارضا کند:

  1. اجتماع تمامی X i {\displaystyle X_{i}} {\displaystyle X_{i}}ها، مجموعهٔ V {\displaystyle V} {\displaystyle V} باشد.
  2. تمامی رئوس (کیف‌های) درخت که شامل راس v ∈ V {\displaystyle v\in V} {\displaystyle v\in V} هستند، تشکیل یک زیردرخت هم‌بند بدهند.
  3. برای هر یال مانند ( u , v ) {\displaystyle (u,v)} {\displaystyle (u,v)} در گراف G {\displaystyle G} {\displaystyle G}، حداقل یک راس (کیف) مانند X i {\displaystyle X_{i}} {\displaystyle X_{i}} در درخت باشد که شامل هر دو راس u {\displaystyle u} {\displaystyle u} و v {\displaystyle v} {\displaystyle v} است.

تجزیهٔ درختی یک گراف، یکتا نیست. بدیهی‌ترین تجزیهٔ درختی، قراردادن تمامی رئوس گراف در یک کیف است که در این صورت هر گراف یک تجزیه با عرض n − 1 {\displaystyle n-1} {\displaystyle n-1} دارد؛ بنابراین برای هر گراف تجزیه‌های درختی متعددی وجود دارد. عرض درختی یک تجزیهٔ درختی، برابر است با سایز بزرگ‌ترین کیف آن منهای یک. عرض درختی یک گراف نیز که با t w ( G ) {\displaystyle tw(G)} {\displaystyle tw(G)} نمایش داده می‌شود، برابرست با کم‌ترین عرض درختی میان تمامی تجریه‌های درختی آن گراف.

مثال: در شکل زیر گراف G {\displaystyle G} {\displaystyle G} و یک تجزیهٔ درختی از آن را می‌بینید. عرض این تجزیهٔ درختی، ۲ می‌باشد.

Thumb
یک گراف به همراه یک تجزیهٔ درختی از آن با عرض ۲یک گراف با هشت راس ، و یک تجزیه‌ی درختی آن با شش گره. هر یال (متشکل از دو راس) از گراف اصلی حداقل در یکی از سبدهای تجزیه‌ی درختی دیده می‌شود (به طور مثال دو راس a و b در گراف اصلی به هم وصل‌اند و بنابراین در تجزیه درختی در حداقل یکی از سبدها (سبد بالا چپ) دیده می‌شوند).از طرفی دیگر تمامی رئوس گراف (۸ راس) در حداقل یکی از سبدهای تجزیه درختی آمده‌اند. شرط سوم نیز برقرار است. بدین معنی که سبدهای حاویِ یک راس، تشکیل یک زیردرخت در تجزیه درختی می‌دهند (به طور مثال به راس G که با رنگ بنفش مشخص شده‌است، دقت کنید که در سه سبد موجود است و این سه سبد تشکیل یک مولفه هم‌بندی می‌دهند). برقراری این سه شرط نشان می‌دهد که تجزیه درختی ارائه‌شده، یک تجزیه درختی معتبر است.

مثال: عرض درختی تمام درخت‌ها برابر با یک است.

تجزیه‌ی درختی نرم

تجزیهٔ درختی ( X i | i ∈ I , T ( I , F ) ) {\displaystyle ({X_{i}|i\in I},T(I,F))} {\displaystyle ({X_{i}|i\in I},T(I,F))} با عرض k نرم می‌گوییم اگر:

  • ∀ i | X i | = k + 1 {\displaystyle \forall i\quad |X_{i}|=k+1} {\displaystyle \forall i\quad |X_{i}|=k+1}
  • ∀ i , j ∈ F | X i ⋂ X j | = k {\displaystyle \forall {i,j}\in F\quad |X_{i}\bigcap X_{j}|=k} {\displaystyle \forall {i,j}\in F\quad |X_{i}\bigcap X_{j}|=k}

نکته: هر تجزیهٔ درختی را می‌توان به یک تجزیهٔ درختی نرم تبدیل کرد.


مجموعه‌ی مستقل بر روی تجزیه‌ی درختی

فرض کنید ( X i | i ∈ I , T ( I , F ) ) {\displaystyle ({X_{i}|i\in I},T(I,F))} {\displaystyle ({X_{i}|i\in I},T(I,F))} یک تجزیهٔ درختی برای گراف G = ( V , E ) {\displaystyle G=(V,E)} {\displaystyle G=(V,E)} باشد به طوری که عرض آن حداکثر k {\displaystyle k} {\displaystyle k} باشد. می‌خواهیم الگوریتمی از O ( k 2 4 k | V | ) {\displaystyle O(k^{2}4^{k}|V|)} {\displaystyle O(k^{2}4^{k}|V|)} ارائه دهیم تا بزرگ‌ترین مجموعهٔ مستقل این گراف را پیدا کنیم.

ابتدا درخت را از راس دلخواه r ریشه دار می‌کنیم. به ازای هر U ⊆ X i {\displaystyle U\subseteq X_{i}} {\displaystyle U\subseteq X_{i}}، d p ( i , U ) {\displaystyle dp(i,U)} {\displaystyle dp(i,U)} را برابر با بزرگ‌ترین مجموعهٔ مستقل که می‌توان در زیر درخت i پیدا کرد به شرط آن که اشتراک راس‌های مجموعهٔ مستقل و X i {\displaystyle X_{i}} {\displaystyle X_{i}} دقیقا راس‌های U باشد تعریف می کنیم. حال الگوریتم جستجوی عمق اول را روی درخت اجرا می ‌کنیم. سپس به ازای هر راس i یکی از کارهای زیر را انجام می دهیم:

  • اگر راس i {\displaystyle i} {\displaystyle i}یک برگ بود، به ازای هر U ⊆ X i {\displaystyle U\subseteq X_{i}} {\displaystyle U\subseteq X_{i}} اگر U یک مجموعهٔ مستقل در گراف بود d p ( i , U ) = | U | {\displaystyle dp(i,U)=\left\vert U\right\vert } {\displaystyle dp(i,U)=\left\vert U\right\vert } در نظر می گیریم در غیر این صورت d p ( i , U ) = − ∞ {\displaystyle dp(i,U)=-\infty } {\displaystyle dp(i,U)=-\infty }
  • اگر راس i {\displaystyle i} {\displaystyle i}برگ نبود و c 1 , c 2 , … , c l {\displaystyle c_{1},c_{2},\dots ,c_{l}} {\displaystyle c_{1},c_{2},\dots ,c_{l}}فرزندان راس i {\displaystyle i} {\displaystyle i}باشند آنگاه:

d p ( i , U ) = | U | + ∑ j = 1 l m a x ( d p ( j , W ) | W ⊆ ( X c j − U ) a n d   W ∪ U   i s   i n d e p e n d e n t ) {\displaystyle dp(i,U)=|U|+\sum _{j=1}^{l}max(dp(j,W)|W\subseteq (X_{c_{j}}-U)\quad and\ W\cup U\ is\ independent)} {\displaystyle dp(i,U)=|U|+\sum _{j=1}^{l}max(dp(j,W)|W\subseteq (X_{c_{j}}-U)\quad and\ W\cup U\ is\ independent)}

جواب نیز برابر خواهد شد با:

m a x ( d p ( r , U ) | U ⊆ X r {\displaystyle max(dp(r,U)|U\subseteq X_{r}} {\displaystyle max(dp(r,U)|U\subseteq X_{r}} تعداد حالاتی که مقادیر آن‌ها را پیدا می‌کنیم برابر با 2 k | V | {\displaystyle 2^{k}|V|} {\displaystyle 2^{k}|V|} است. هم‌چنین برای به دست آوردن مقدار یک خانه باید به ازای تمام زیرمجموعه از بسته‌های فرزندانش مقدار ماکسیمم حساب شود و همچنین باید بررسی شود که راس‌ها به هم یال نداشته باشند که مرتبهٔ این قسمت نیز از O ( 2 k k 2 ) {\displaystyle O(2^{k}k^{2})} {\displaystyle O(2^{k}k^{2})} است. در نتیجه زمان اجرای الگوریتم O ( k 2 4 k | V | ) {\displaystyle O(k^{2}4^{k}|V|)} {\displaystyle O(k^{2}4^{k}|V|)} خواهد شد.

به ازای k‌های کوچک اثبات شده‌است که گرافی که مجموعهٔ گراف‌های زیر را به عنوان ماینور شامل نمی شود ، عرض درختی کمتر مساوی k دارد.

  • k = 0 → k 2 {\displaystyle k=0\rightarrow k_{2}} {\displaystyle k=0\rightarrow k_{2}}
  • k = 1 → k 3 {\displaystyle k=1\rightarrow k_{3}} {\displaystyle k=1\rightarrow k_{3}}
  • k = 2 → k 4 {\displaystyle k=2\rightarrow k_{4}} {\displaystyle k=2\rightarrow k_{4}}
  • k = 3 → k 5 , k 2 , 2 , 2 {\displaystyle k=3\rightarrow k_{5},k_{2,2,2}} {\displaystyle k=3\rightarrow k_{5},k_{2,2,2}}
  • k = 4 → {\displaystyle k=4\rightarrow } {\displaystyle k=4\rightarrow } بیش از ۷۵ نوع گراف [1]

در حالت کلی، پاسخ به این سؤال که آیا گراف G {\displaystyle G} {\displaystyle G} عرض درختی‌اش حداکثر k {\displaystyle k} {\displaystyle k} است یا نه یک مسئله N P − c o m p l e t e {\displaystyle NP-complete} {\displaystyle NP-complete} (ان‌پی کامل) است. اما برای k {\displaystyle k} {\displaystyle k}های مشخص با اندازهٔ کوچک الگوریتمی با زمان اجرای خطی وجود دارد. زمان اجرای این الگوریتم بر اساس سایز ورودی خطی ولی بر اساس k {\displaystyle k} {\displaystyle k} نمایی‌ست و لذا فقط برای k {\displaystyle k} {\displaystyle k}های ثابت و کوچک عملی‌ است.[2] [3] [4]

به بیان دقیق‌تر محسابه‌ی عرض درختی یک مساله FPT است که مخفف Fixed-Parameter Tractable می‌باشد. به مساله‌ای FPT گفته می‌شود که زمان اجرای آن به صورت f ( k ) n O ( 1 ) {\displaystyle f(k)n^{{\mathcal {O}}(1)}} {\displaystyle f(k)n^{{\mathcal {O}}(1)}} باشد که در آن n {\displaystyle n} {\displaystyle n} سایز وروردی (در این مساله ː اندازه گراف)، k {\displaystyle k} {\displaystyle k} یک پارامتر (در این‌ مساله ː عرض درختی) و f ( ⋅ ) {\displaystyle f(\cdot )} {\displaystyle f(\cdot )} یک تابع محاسبه‌پذیر است (هر تابعی که حداقل یک ماشین تورینگ در زمان متناهی بتواند آن را محاسبه کند). جدول زیر خلاصه‌ای از الگوریتم‌های حل مساله‌ی عرض درختی‌ست. به جز موارد ردیف اول و ردیف نهم، باقی الگورتیم‌ها همگی FPT می‌باشند که در آن‌ها ضریب تخمین، وابستگی به k {\displaystyle k} {\displaystyle k} در پیچیدگی زمانی یا همان f ( k ) {\displaystyle f(k)} {\displaystyle f(k)} و وابستگی به n {\displaystyle n} {\displaystyle n} در پیچیدگی زمانی در ستون‌های متفاوت ذکر شده‌اند.

اطلاعات بیشتر , ...
ضریب تخمین وابستگی زمان اجرا به k وابستگی زمان اجرا به n مرجع
دقیق (۱) O ( 1 ) {\displaystyle {\mathcal {O}}(1)} {\displaystyle {\mathcal {O}}(1)} O ( n k + 2 ) {\displaystyle {\mathcal {O}}(n^{k+2})} {\displaystyle {\mathcal {O}}(n^{k+2})} آرنبرگ و سایرین (۱۹۸۷)
۴ O ( 3 3 k ) {\displaystyle {\mathcal {O}}(3^{3k})} {\displaystyle {\mathcal {O}}(3^{3k})} O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} {\displaystyle {\mathcal {O}}(n^{2})} رابرتسون و سیمور (۱۹۹۵)
۸ 2 O ( k log ⁡ k ) {\displaystyle 2^{{\mathcal {O}}(k\log k)}} {\displaystyle 2^{{\mathcal {O}}(k\log k)}} n log 2 ⁡ n {\displaystyle n\log ^{2}n} {\displaystyle n\log ^{2}n} رید (۱۹۹۲)
۵ 2 O ( k log ⁡ k ) {\displaystyle 2^{{\mathcal {O}}(k\log k)}} {\displaystyle 2^{{\mathcal {O}}(k\log k)}} n log ⁡ n {\displaystyle n\log n} {\displaystyle n\log n} لاگرگرن (۱۹۹۶)
دقیق (۱) 2 O ( k 3 ) {\displaystyle 2^{{\mathcal {O}}(k^{3})}} {\displaystyle 2^{{\mathcal {O}}(k^{3})}} O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)} بُدلَندِر (۱۹۹۶)
O ( log ⁡ k ) {\displaystyle {\mathcal {O}}({\sqrt {\log k}})} {\displaystyle {\mathcal {O}}({\sqrt {\log k}})} O ( 1 ) {\displaystyle {\mathcal {O}}(1)} {\displaystyle {\mathcal {O}}(1)} n O ( 1 ) {\displaystyle n^{{\mathcal {O}}(1)}} {\displaystyle n^{{\mathcal {O}}(1)}} فیگه و سایرین (۲۰۰۸)
۴.۵ 2 3 k {\displaystyle 2^{3k}} {\displaystyle 2^{3k}} n 2 {\displaystyle n^{2}} {\displaystyle n^{2}} امیر (۲۰۱۰)
۴.۶۶ 2 3.6982 k {\displaystyle 2^{3.6982k}} {\displaystyle 2^{3.6982k}} n 3 log 4 ⁡ n {\displaystyle n^{3}\log ^{4}n} {\displaystyle n^{3}\log ^{4}n} امیر (۲۰۱۰)
دقیق (۱) O ( 1 ) {\displaystyle {\mathcal {O}}(1)} {\displaystyle {\mathcal {O}}(1)} O ( 1.734 n ) {\displaystyle {\mathcal {O}}(1.734^{n})} {\displaystyle {\mathcal {O}}(1.734^{n})} فومین و سایرین (۲۰۱۵)
۳ 2 O ( k ) {\displaystyle 2^{{\mathcal {O}}(k)}} {\displaystyle 2^{{\mathcal {O}}(k)}} O ( n log ⁡ n ) {\displaystyle {\mathcal {O}}(n\log n)} {\displaystyle {\mathcal {O}}(n\log n)} بُدلَندِر (۲۰۱۶)
۵ 2 O ( k ) {\displaystyle 2^{{\mathcal {O}}(k)}} {\displaystyle 2^{{\mathcal {O}}(k)}} O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)} بُدلَندِر (۲۰۱۶)
k {\displaystyle k} {\displaystyle k} O ( k 7 ) {\displaystyle {\mathcal {O}}(k^{7})} {\displaystyle {\mathcal {O}}(k^{7})} O ( n log ⁡ n ) {\displaystyle {\mathcal {O}}(n\log n)} {\displaystyle {\mathcal {O}}(n\log n)} فومین و سایرین (۲۰۱۸)
۵ 2 7.651 k {\displaystyle 2^{7.651k}} {\displaystyle 2^{7.651k}} O ( n log ⁡ n ) {\displaystyle {\mathcal {O}}(n\log n)} {\displaystyle {\mathcal {O}}(n\log n)} بلباسی و فورِر (۲۰۲۱-آ)
۲ 2 O ( k ) {\displaystyle 2^{{\mathcal {O}}(k)}} {\displaystyle 2^{{\mathcal {O}}(k)}} O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)} کُرهُنِن (۲۰۲۱)
۵ 2 6.755 k {\displaystyle 2^{6.755k}} {\displaystyle 2^{6.755k}} O ( n log ⁡ n ) {\displaystyle {\mathcal {O}}(n\log n)} {\displaystyle {\mathcal {O}}(n\log n)} بلباسی و فورِر (۲۰۲۱-ب)
بستن

در این مثال در یک گراف تعدادی پلیس حضور دارند که در راس‌های مختلف گراف قرار دارند. یک دزد نیز در یکی از راس‌های گراف پنهان شده‌است. در هر مرحله اگر k پلیس داشته باشیم ، پلیس‌ها k راس را در نظر می‌گیرند و به آن می‌روند. سپس دزد یک راس را در نظر می‌گیرد که در آن پلیس نیست و از راسی که در آن حضور دارد به راس مقصد مسیری وجود داشته باشد که راس‌های این مسیر شامل راس‌های اشتراک مکان‌های قبلی پلیس‌ها و مکان‌های جدید پلیس‌ها نباشد. پلیس‌ها برنده می‌شوند اگر بعد از تعداد محدودی مرحله ، دزد راسی برای فرار کردن به آن نداشته باشد.

قضیه : اگر عرض درختی گراف G حداکثر k باشد ، آنگاه 1 + k پلیس می توانند دزد را دستگیر کنند.

اثبات: چون عرض درختی گراف حداکثر k است ، یک تجزیهٔ نرم برای آن وجود دارد. حال تجزیهٔ نرم آن را در نظر می گیریم. ابتدا آن را از راسی ریش‌دار می کنیم. پلیس‌ها در مرحله اول در 1 + k راس در بستهٔ ریشه قرار می‌گیرند. دزد نیز در این مرحله در راسی دیگر قرار گرفته‌است. حال راسی که دزد در آن قرار گرفته را در نظر می‌گیریم. مجموعهٔ بسته‌هایی که راس دزد در آن قرار دارد یک مجموعهٔ همبند در یکی از زیر درخت‌های فرزندان ریشه است. پلیس‌ها در این مرحله آن فرزند را انتخاب می‌کنند و به راس‌های آن منتقل می‌شوند و از آن جا که اشتراک بستهٔ جدید با بستهٔ قبل k است و یک برش در گراف را تشکیل می‌دهد ، دزد نمی‌تواند از آن خارج شود. اگر پلیس‌ها به همین روند ادامه دهند در آخر دزد را در یک بسته برگ گیر می‌اندازند. [5] [6]

  1. [1]
    https://www.ti.inf.ethz.ch/ew/lehre/GA07/lec-treewidth.pdf
  2. [2]
    Bodlaender, Hans L. (1996), "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing, 25 (6): 1305–1317
  3. [3]
    A $c^k n$ 5-Approximation Algorithm for Treewidth Read More: https://epubs.siam.org/doi/abs/10.1137/130947374
  4. [4]
    https://arxiv.org/abs/2104.07463
  5. [5]
    «نسخه آرشیو شده» (PDF). بایگانی‌شده از اصلی (PDF) در ۲۷ سپتامبر ۲۰۱۶. دریافت‌شده در ۲۰ مه ۲۰۱۷.
  6. [6]
    https://epubs.siam.org/doi/abs/10.1137/130947374
Edit in WikipediaRevision historyRead in Wikipedia

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Chrome
Wikiwand for Chrome
Edge
Wikiwand for Edge
Firefox
Wikiwand for Firefox

تجزیه‌ی درختی

الگوریتم‌های محاسبهٔ عرض درختی یک گراف

مسئله‌ی دزد و پلیس‌ها

منابع