نویسه جدید وبلاگ
گراف يک ساختمان داده غير خطی است که کاربردهای وسيعی دارد. در اين بخش برخی از اصطلاحات نظريه گراف ، روش های نمايش و عمليات روی گراف آورده شده است.
تعاریف گراف
يک گراف شامل دو مجموعه است؛ مجموعه غير تهی از گره ها يا رئوس (vertex) و مجموعه ای از يال ها (edge) که راس ها را به هم متصل می کنند.
مثال. می توان شهر های يک کشور را رئوس و جاده های بين آن ها را يال های يک گراف تصور کرد.
به هر راس يا هر يال گراف نامی اختصاص داده می شود.
يک گراف تهی (null graph) گرافی است که تنها شامل راس است و مجموعه يال های آن تهی است يعنی يالی ندارد.
جهت
يک گراف می تواند به دو شکل جهتدار(directed) يا غيرجهتدار (undirected) باشد.
يک گراف جهتدار گرافی است که جهت هر يال در آن تعيين شده است. در گراف جهتدار ترتیب رئوس در هر يال اهمیت دارد و یال ها با پیکان هائی از راس ابتدا به راس انتها رسم می شوند. در گراف غيرجهتدار می توان در هر دو جهت بين راس ها حرکت کرد و ترتيب راس های يال اهميت ندارد.
دانلود pdf مقاله از سرور 1
دانلود pdf مقاله از سرور 2
source
