امير غفوريان

کارشناسی ارشد سازه دانشگاه فردوسی مشهد

مقدمه

مرتب كردن گرهي براي كاهش پهناي نوار

مثال

مراجع

در روش حذفي گوس زمان لازم براي حل دستگاه معادلات به روش ماتريس نواري، با مربع پهناي نوار متناسب است. روشهاي گوناگوني براي حل دستگاه معادلات يك سيستم نواري وجود دارد كه بدين منظور مي‌توان به مرجع [1]‌مراجعه نمود. كم كردن پهناي نوار علاوه بر كاهش حجم عمليات محاسباتي، سبب كم نمودن حافظه رايانه‌اي مورد نياز و همچنين كاهش خطاي گرد كردن مي‌شود.

شيوه‌هاي مختلفي براي كاهش پهناي نوار از جمله جابجا كردن سطرها و ستونهاي ماتريس پيشنهاد شده است كه بيشتر آنها غيراقتصادي مي‌باشد. اولين روش مستقيم براي كاهش پهناي نوار بوسيله « هاروي » پيشنهاد شده است :

چگونه در يك گراف S‌ با N(S)‌گره، گره‌ها را شماره گذاري كنيم بگونه‌اي كه بيشينه قدرمطلق تفاضل ميان گره‌هاي مجاور، كمينه گردد

در حالت خاص كه p=q=b و براي هر i و j كه | i –j | > b ، a_ij=0 باشد، b‌را پهناي نيم‌نوار و 2b+1 را پهناي نوار ماتريس A=[a_ij] گويند.

پهناي نوار ماتريس يك سازه بطور مستقيم با پهناي نوار ماتريس مجاورت گراف مربوط به آن سازه متناسب است. اگر A ماتريس مجاورت گراف S و i,j گره‌هاي يال k ام اين گراف باشند، با تعريف a_k=|i-j| پهناي نوار A به صورت زير خواهد بود :

b(A)=2Max{a_k : k=1,2,…,M(S)}+1

كه M(S)‌تعداد يالهاي گراف S مي‌باشد.

بنابراين با يك شماره‌گذاري بهينه سازه ( يا گراف متناظر با آن ) مي‌توان پهناي نوار ماتريس منحني مربوط به آن را كمينه كرد.

يكي از روشهاي شماره‌گذاري بهينه يك گراف ‌با استفاده از درخت كوتاهترين مسير يا SRT ميسر است.

درخت كوتاهترين مسير با ريشهn₀ درختي‌است كه فاصله ميان هرگره n_j آن ازn_j كمينه اين درخت با الگوريتم ساده زير مي‌توان بنا نهاد :

ريشه انتخابي را n₀ مي‌ناميم و به گره‌هاي مجاور آن برچسب « 1 » را منسوب مي‌كنيم. يال‌هايي كه هر گره n₀مرور مي‌كند را به درخت الحاق مي‌كنيم. انتهاي ديگر تمامي يالهايي را كه بر گره‌هاي با برچسب « 1 » مرور مي‌كنند و برچسب ندارند را ، عدد « 2 » برچسب‌گذاري مي‌كنيم. همچنين يالهاي متناظر آنها را به درخت الحاق مي‌كنيم. اين روند را تا آنجا كه تمامي گره‌هاي گراف برچسب گذاري شوند ادامه‌مي‌دهيم :

Top

Top

يك SRT‌مجموعه گره‌هاي گراف S‌را به زيرمجموعه‌هايي برحسب فاصله‌شان از ريشه n₀ افراز مي‌كند.

هريك از اين زير مجموعه‌ها را يك «كانتور» (Contour) درخت كوتاهترين مسير مي‌ناميم كه با C_i نمايش مي‌دهيم.

يك گره آغاز شايسته انتخاب كنيد

مجموعه‌گره‌هاي گراف S را به كانتورهاي مجزا افراز كنيد. ( گره‌هاي با برچسب يكسان در يك كانتور قرار مي‌گيرند )

يك مسير همبند شامل يك گره نماينده از هر كانتور بنا نهيد.

گره‌هاي هر كانتور را براي بدست آوردن شماره‌گذاري گرهي نهايي مرتب كنيد.

فاصله d(ni,nj) ميان دو گره ni,nj بصورت طول كوتاهترين مسير ميان اين دو نقطه تعريف مي‌گردد. همچنين خروج از مركزيت گره nj بصورت زير مشخص مي‌شود :

قطر گراف S‌بصورت زير تعريف مي‌شود :

يك نقطه خوب مي‌تواند نقطه‌اي باشد كه خروج از مركزيت آن با قطر گراف برابر يا نزديك آن باشد.

اگر A‌ماتريس مجاورت گراف S باشد، ماتريس Q‌به صورت زير تعريف مي‌شود :

Q=A+I

I ماتريس

هماني مي‌باشد. ماتريس Q‌ يك ماتريس معين مثبت است و همچنين تمامي درايه‌هاي

مثبت مي‌باشند.

اگر  بردار ويژه متناظر با

اگر		آنگاه

اگر

باشد، به راحتي قابل اثبات و مشاهده است كه مؤلفة i ام

برابر تعداد گامهاي (Walk) با طول k وكمتر است كه از هر نقطه اختياري گراف S

شروع به

ختم مي‌شود.

بنابراين با ميل دادن به سمت بينهايت

مي‌توانيم به يك مقدار عددي متوسط براي گامهايي كه از يك گره مي‌گذرد، دست يابيم

. اين معيار را شاخص دسترسي نام مي‌نهيم. با يك  يك‌ سازي مناسب

به سمت بزرگترين بردار ويژه Q ميل مي‌كند. يك روش پيداكردن نقطه شروع مناسب، با ا

لگوريتم زير بيان مي‌شود :

بردار ويژه متناظر با بزرگترين مقدار ويژه ماتريس Q را بيابيد. (W_i)

كمترين مقدار W_i از بردار W₁ را پيدا كنيد. گره مربوط به اين مؤلفه را به عنوان يگ گره شروع خوب درنظر بگيريد.

چند روش ديگر پيدا كردن يك نقطه شروع خوب در مرجع [2] آورده شده است.

يك پيمايش عرضي از SRT بصورت يك مسير همبند p شامل يك گره از هر كانتور از SRT تعريف مي‌گردد. يك پيمايش عرضي مينيمال پيمايشي است كه مجموع درجه‌هاي گرهي آن كمينه گردد. سعي بر اينست كه پيمايش عرضي انتخاب شده، يك پيمايش عرضي مينيمال باشد. همچنين وزن گره را برابر مقدار در تعريف مي‌كنيم. يك الگوريتم براي بنيان نهادن چنين پيمايشي به صورت زير است :

اگر كانتورهاي SRT باشند،را درايه‌هاي مربوط به گره‌هاي تعريف مي‌كنيم.

گام نخست : به گره شروع ( ريشه ) برچسب را اختصاص مي‌دهيم و اين گره را به عنوان وزن جديد آن كه با نمايش مي‌دهيم، انتخاب مي‌كنيم.

گام دوم : وزن جديد هر گره را با اضافه نمودنها از به محاسبه مي‌كنيم.

گام سوم : روند گام دو را با محاسبه براي هر گره تكرار مي‌كنيم.

گام چهارم : را با كمينه وزن از آخرين كانتور درخت كوتاهترين مسير انتخاب مي‌كنيم.

گام پنجم : را از كه به با يك شاخه متصل است، انتخاب مي‌كنيم.

گام ششم : با تكرار گان پنجم، را از فاكتورهاي بدست مي‌آوريم.

Top

گام نخست : به عدد 1 را منسوب مي‌كنيم.

گام دوم : به عدد 2 را اختصاص مي‌دهيم و يك زير درخت كوتاهترين مسير بر روي بنا مي‌نهيم. گره‌هاي كانتور را برحسب برچسبشان در اين زيردرخت مرتب مي‌كنيم.

گام سوم : ر.ند گام دوم را براي شماره گذاري  ‌  كانتورهاي با بكار بردن پي‌ در  پي به صورت گره‌  هاي شروع زيردرخت كوتاهترين مسير تكرار مي‌  كنيم تا آنجا كه    تمامي گره‌ هاي   S   شماره‌گذاري   شوند.

مثال : گراف زير و شماره‌گذاري نخستين آنرا در نظر مي‌گيريم :

همچنين پيمايش عرضي انتخاب شده، مسيري است كه از گره‌هاي زير عبور مي‌كند :

{ 19 , 13 , 7 , 1 , 2 , 3 , 4 , 5 , 6 }

بنابراين پاسخ اين مثال به شكل زير خواهد بود :

براي يك نمونه گراف ديگر، پيمايش عرضي و بهينه شماره‌گذاري به صورت زير مي‌باشد :

[1] golub.G.h & Von Loon . C.F. “Matrix Computation” . Johns Hopkins university press , Battimore , MD , 1983

[2] Kaveh.A “Structural Mechanics , Graph & Matrix Methods” . Reasearch studies LTD , 1995