درخت اس پی کیوار

دانشنامه عمومی

درخت اس پی کیوآر. در نظریهٔ گراف، یکی از زیرشاخه های ریاضیات، مولفه های سه همبند یک گراف دوهمبند یک دستگاه از گراف های کوچک تر است که همهٔ برش های دوراسی گراف را توصیف می کند. درخت SPQR یک داده ساختار درختی است که در علوم رایانه، به ویژه در الگوریتم های گراف، برای نشان دادن مولفه های سه همبند یک درخت استفاده می شود. درخت SPQR یک گراف را می توان در یک زمان خطی بنا کرد. این گراف کاربردهای متعددی در الگوریتم های پویای رنگ آمیزی گراف دارد. ساختارهای بنیادین درخت SPQR، مؤلفه های سه همبند گراف، و اتصال بین این اجزا و تعبیهٔ مسطح یک گراف مسطح، را اولین بار ساندرز مک لین ( 1973 ) بررسی کرد. پژوهشگران دیگری همچون دی باتیستا وتاماسیا این ساختارها را، پیش از رسمی شدن به عنوان درخت SPQR در الگوریتم های کارآمد استفاده کرده بودند.
یک درخت SPQR فرم یک درخت بدون ریشه را دارد که در آن هر گره x با یک گراف بدون جهت یا یک گراف چندگانه Gx متناظر شده است. گره و گراف متناظر با آن یکی از 4 فرم زیر را داراست:
• در یک گرهٔ S، گراف متناظر یک گراف دوری با بیشتر از 2 راس یا یال است. این مورد مشابه ترکیب سری در گراف های سری - موازی است؛ S نشان دهندهٔ سری ( series ) است.
• در یک گرهٔ P، گراف متناظر یک گراف دوقطبی ( یک گراف چندگانه دارای دو راس با تعداد یال بیشتر از 2 ) است. یک همزاد مسطح ( Planar Dual ) برای یک گراف دوری. این مورد مشابه ترکیب موازی در گراف های سری - موازی است؛P نشان دهندهٔ موازی ( parallel ) ) است.
• در یک گرهٔ Q، گراف متناظر یک یال تنها دارد. این مورد جزئی تنها برای گراف هایی که یک راس دارند به کار برده می شود و در گراف های پیچیده تر ظاهر نمی شود.
• در یک گرهٔ R، گراف متناظر یک گراف سه همبند است که دوری با دوقطبی نباشد. R نشان دهندهٔ صلب ( rigid ) است: در کاربرد درخت SPQR در تعبیهٔ گراف مسطح، گراف متناظر با یک گرهٔ R یک تعبیهٔ مسطح منحصربه فرد دارد.
هر یال xy بین دو گرهٔ درخت SPQR متناظر با دو یال جهت دار مجازی است که یکی از آن ها یک یال در Gx و دیگری یالی در Gy است. هر یال در یک گراف Gx می تواند حداکثر در یک درخت SPQR یال مجازی باشد.
یک درخت SPQR، T، یک گراف دوهمبند GT را نمایش می دهد که اینگونه ساخته می شود: هرگاه یال xy در درخت SPQR، یال مجازی ab، در گراف Gx را با یال مجازی cd، در Gy متناظر کند، یک گراف بزرگتر با ادغام کردن a و c و ساختن یک راس فوقانی و ادغام کردن b و d و ساختن راس فوقانی دیگر و حذف دو یال مجازی ساخته می شود. با این کار گراف بزرگتر جمع دو گروهکی ( Clique - sum ) برای دو گراف Gx و Gy است. با انجام این گام برای هر یال درخت SPQR گراف GT ساخته می شود، ترتیب این گام ها تأثیری در نتیجهٔ نهایی ندارد. هر راس در گراف Gx با یک راس منحصربه فرد در GT متناظر می شود. ( راس فوقانی که از ادغام این راس به وجود آمده است. )
عکس درخت اس پی کیوآر
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران