گراف

چكيده:

علم رياضيات نقش حياتي  راد ر زمينه هاي مختلف دارد يكي از مفاهيم مهم در ر ياضيات نظريه گراف مي باشد كه در مدل هاي ساختاري استفاده مي شود.

دراين مقاله سعي شده به اهميت وكاربردگراف در كامپيوتر پرداخته شود.گراف در موارد زيادي در دنياي كامپيوتر كاربرد دارد كه  از اين موارد مي توان به كاربردهاي ان در شبكه ،الگوريتم وطراحي ها اشاره نمود.

كليد واژه:كامپيوتر،گراف،كاربرد گراف در كامپيوتر،تاثير گراف بر كامپيوتر

مقدمه

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اویلر ریاضیدان بزرگ مفهوم گراف  رادر سال ۱۷۳۶ برای حل مسئله پل‌های کونیگسبرگ (Konigsberg) ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بوده‌است.

از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش در آورد.

كاربرد گراف در علوم كامپيوتر

نظريه گراف وگراف در قسمتهاي مختلف علم كامپيوتر ورايانه كاربرد دارد كه  عبارتند از:

-حل مسايل كامپيوتري

-نمايش ساختار ها(برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد)

-استفاده از گراف در طراحي شبكه كامپيوتري

-استفاده از گراف در الگوريتم ها(الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و…)

-استفاده از گراف در درخت ها وماتريس درخت ها

-استفاده از گرافها به عنوان كدهاي كمكي

-كاربرد گراف در توپولوژي شبكه

-كاربردهاي نرم افزاري

-استفاده تحقيقاتي

مزاياي گراف

گراف‌ها دارایی مزایای مختلفی هستند که شفاف تر کردن و واضحتر کردن تصویر و کاهش مصرف CPU به عنوان یکی از اصلی‌ترین مزایای آنها بشمار می‌رود.

كاربردهاي نرم افزاري

در برخي از كاربردهاي گراف در كامپيوتر كاربردهاي نرم افزاري وشغلي مي باشد كه به نوعي به طور غير مستقيم  با كامپيوتر درارتباط است مثلا طراحی مدارهای الکتریکی، اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک، و….

استفاده از گرافها به عنوان كدهاي كمكي

از گرافها می‌توان به عنوان کدهای کمکی نام برد که به DVB Playerها در بالا بردن قابلیت‌های آنها کمک می‌کنند.

استفاده تحقيقاتي

از استفاده هاي تحقيقاتي گراف در علوم كامپيوتر مي توان  به مواردي چون داده كاوي،تقسيم بندي تصاوير،خوشه،ضبط تصوير،شبكه وغيره اشاره داشت.

استفاده از گراف در طراحي شبكه كامپيوتري

مهم ترين كاربرد ان در شبكه در رنگ اميزي  رئوس ولبه هاي ساختار درختي در شبكه براي تخصيص منابع مي باشد وهمچنين در مسير هاي پياده سازي مدارات تئوري گراف فايده زيادي دارد.

استفاده از گراف در الگوريتم ها

نقش عمده تاثير گراف در علوم كامپيوتر مربوط به كاربرد گراف در الگوريتم هاست برخي از اين الگوريتم ها عبارتند از:

۱٫الگوریتم کوتاه ترین مسیر در یک شبکه

 2. پیدا کردن یک درخت پوشا حداقل
۳٫ پیدا کردن گراف

 4 planarity. الگوریتم برای پیدا کردن ماتریس مجاورت.
۵٫ الگوریتم پیدا کردن ارتباط

 6. الگوریتم پیدا کردن دور در گراف
۷٫ الگوریتم های جستجو برای یک عنصر در یک ساختار داده ها (DFS، BFS) و غیره

زبان هاي كامپيوتري مختلف  براي حمايت از مفاهيم گراف استفاده مي شود هدف اصلي اين زبانها ،ايجاد توانايي براي كاربران براي تدوين وفرموله كردن عمليات بر روي نمودار به صورت جمع وجور ونرمال.

برخي از اين زبانها عبارتنداز:

Spantreeبراي پيدا كردن يك درخت پوشا در گراف داده شده

)Gtplنمودار زبان تئوري)

Hint(اشاره) فرمتي ازlisp

فرمتgraspeازlisp

Igtsفرمتي از فرترن

Geaگرافيك  خاص الگول(قالبي از زبان الگول)

حوزه براي دستكاريdigraphsها

نمودار بازيابي اطلاعات زبان

Fgraalزبان فرترن نمودار توسعه يافته الگوريتم

استفاده از تكنيك هاي شمارش گراف

 اين تكنيك براساس فرمول شيميايي وقوانين چند ظرفيتي براي هرگونه توليد ماده،وشناسايي تركيبات شيميايي به طور خودكار  بوسيله زبان كامپيوتريdendral ميباشد.

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

در دنياي امروز امنيت شبكه كامپيوتري يكي از ملزومات  استفاده  از اينترنت با خيالي آسوده مي باشد. سهم گراف در اين عرصه نيز مهم است. شبيه سازي انتشار كرم هاي مخفي در شبكه هاي كاميوتري بزرگ وهمچنين طراحي استراتژي بهينه براي حفاظت از شبكه در برابر حملات ويروسي  است.

كاربرد گراف مربوط به ad hoc

گراف در اين زمينه در قسمتهايي چون اتصال هاي شبكه اي،مسير يابي مدل سازي شبكه  وشبيه سازي استفاده مي شود از انجايي كه گراف ساختاري نموداري دارد مي توان ازان در تجزيه وتحليل استفاده كرد.

در تحليل رايانه اي ساز ه ها، تحليل بايد به صورتي انجام پذير د كه علاوه بر كاهش فضاي كامپيوتر و زمان اجراي محاسباتي كامپيوتر خطاهاي محاسباتي نيز به كمترين مقدار ممكن برسد اين امر با تشكيل ماتريسهاي ساز ه اي مناسب كه در حين پر صفر و خوش ساختار بودن خوش حالت نيز ميباشد، تحقق خواهد يافت.

برگرفته از مقاله

 APPLICATIONS OF GRAPH THEORY IN COMPUTER SCIENCE AN OVERVIEW

S.G.Shirinivas, Dept of Computer Applications Chettinad College of Engineering and Technology Karur ,Tamilnadu,India-639114.

 S.Vetrivel Dept of Computer Applications. Chettinad College of Engineering and Technology Karur ,Tamilnadu,India-639114

Dr. N.M.Elango  Professor, Dept of Computer Applications.

Oxford College of Engineering, Bangalore

References:

] Adam Schenker, Mark Last, horst Banke,Abraham andel,”Clustering of Web documents using a graph model”, Springer werlog,

Septermber 2007.

Anindya J.Pal, Samar S.Sarma, Biman Ray, “CCTP, Graph Coloring algorithms – Soft computing Solutions IEEE, 2007

Bing Hong Liu, Wel Chieh Ke, Chin-Hsien Tsai, Ming-Jer Tsai, “Constructing a message pruning tree with minimum cost for tracking

moving objects in wireless sensor networks”, IEEE Volume 57, Number 6, July 2008

Daniel Marx, “Graph Coloring problems and their applications in scheduling”,

Gian Luca Marcialis, Fabio Roli, Alessandra Serrau, “Graph Based and Structural Methods for Fingerprint Classification, Springer verlag,

Berlin Heidelberg 2007

John.P.Hayes, “A graph Model for Fault Tolerant Computing Systems”, IEEE September 1976

Narasingh Deo, “Graph theory with applications to engineering and computer science”, Prentice Hall of India, 1990.

Perri Mehonen, Janne Riihijarvi, Marina Petrova, “Automatic Channel allocation for small wireless area networks using graph coloring

algorithm approach”, IEEE 2004

Shariefuddin Pirzada and Ashay Dharwadker, “Journal of the Korean Society for Industrial and applied Mathematics, Volume 11, No.4,

۲۰۰۷

] Sven Dickinson, Pelillo, Ramin Zabih, “Introduction to the special section on graph algorithms in computer vision”, IEEE on pattern

analysis, Vol 23 No. 10, September 2001

V.P.Eswaramoorthy, “New algorithm for analyzing performance of neighbourhood strategies in solving job shop scheduling problems,

Journal of Scientific & Industrial Research, August 2008

Zongheng Zhou,Samir Das, Himanshu Gupta, “Connected K-Coverage Problem in Sensor Networks”

http://www.britinaca.com/bps/additionalcontent/18/33373769/concepts-of-graph-theory-relevant-to-Adhoc-Networks

://www.dharwadker.org/vertex_cover/

http://www.icaen.uiowa.edu/~dip/LECTURE/Understanding6.html

wj:math.sfsu.edu/beck/teach

wikipedia.org/wiki/Median graph

http://en.wikipedia.org/wiki/Bipartite_graph

pedia.org/wiki/Voronoi_diagram

http://en.wikipedia.org/wiki/K-means_clustering
http://en.wikipedia.org/wiki/Geometric_spannerWiki

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *