رسم گراف

**ترسیم گراف** حوزه‌ای از ریاضیات و علوم کامپیوتر است که روش‌های تئوری نمودار هندسی و تجسم اطلاعات را برای به دست آوردن تصاویر دو بعدی از گراف‌ها که از کاربردهایی مانند تجزیه و تحلیل شبکه‌های اجتماعی، کارتوگرافی، زبان‌شناسی و بیوانفورماتیک ناشی می‌شود، ترکیب می‌کند.

ترسیم گراف یا گراف شبکه نمایش تصویری رئوس و لبه‌های یک گراف است. این طراحی نباید با خود گراف اشتباه گرفته شود: طرح‌بندی‌های بسیار متفاوت می‌توانند با یک گراف مطابقت داشته باشند. به‌طور انتزاعی، تنها چیزی که اهمیت دارد این است که کدام جفت رئوس توسط یال‌ها به هم متصل شده‌اند. با این حال، در بتن، چیدمان این رئوس و لبه‌ها در یک نقشه بر درک، قابلیت استفاده، هزینه ساخت و زیبایی‌شناسی آن تأثیر می‌گذارد. اگر گراف در طول زمان با افزودن و حذف یال‌ها تغییر کند (طراحی گراف پویا) مشکل بدتر می‌شود و هدف حفظ نقشه ذهنی کاربر است.

## قراردادهای گرافیکی
گراف‌ها اغلب به عنوان گراف‌های پیوند گره ترسیم می‌شوند که در آن رئوس به صورت دیسک، جعبه یا برچسب‌های متنی و یال‌ها به صورت پاره خط، چند خط یا منحنی در صفحه اقلیدسی نمایش داده می‌شوند. گراف‌های پیوند گره را می‌توان به آثار شبه یوی قرن ۱۴ تا ۱۶ که با نام رامون یوی منتشر شده بود، بازمی‌گردد. شبه یوی نمودارهایی از این نوع را برای نمودارهای کامل به منظور تجزیه و تحلیل تمام ترکیبات زوجی در میان مجموعه‌ای از مفاهیم متافیزیکی ترسیم کرد.

در مورد نمودارهای جهت دار، نوک پیکان‌ها یک قرارداد گرافیکی رایج را تشکیل می‌دهند تا جهت خود را نشان دهند؛ با این حال، مطالعات کاربر نشان داده‌است که قراردادهای دیگر مانند مخروطی کردن این اطلاعات را به‌طور مؤثرتری ارائه می‌دهند. ترسیم مسطح رو به بالا از این قرارداد استفاده می‌کند که هر یال از یک راس پایین‌تر به یک راس بالاتر جهت‌گیری می‌شود و نوک پیکان را غیرضروری می‌کند.

قراردادهای جایگزین برای نمودارهای پیوند-گره شامل نمایش مجاورتی مانند بسته‌بندی دایره ای است که در آن رئوس با نواحی مجزا در صفحه و یال‌ها با مجاورت‌های بین نواحی نشان داده می‌شوند. نمایش‌های تقاطع که در آن رئوس با اجسام هندسی غیر متمایز و یال‌ها با تقاطع آنها نشان داده می‌شوند. نمایش‌های دید که در آن رئوس با نواحی در صفحه و لبه‌ها با مناطقی نشان داده می‌شوند که یک خط دید بدون مانع نسبت به یکدیگر دارند. نقشه‌های همرو، که در آن لبه‌ها به صورت منحنی‌های صاف در ریل‌های قطار ریاضی نمایش داده می‌شوند. پارچه‌هایی که در آن گره‌ها به صورت خطوط افقی و لبه‌ها به‌عنوان خطوط عمودی نشان داده می‌شوند؛ و تجسم‌هایی از ماتریس مجاورت گراف.

## معیارهای کیفیت
در تلاش برای یافتن ابزارهای عینی برای ارزیابی زیبایی‌شناسی و قابلیت استفاده، معیارهای کیفی مختلفی برای طراحی‌های گراف تعریف شده‌اند. علاوه بر هدایت انتخاب بین روش‌های طرح‌بندی مختلف برای یک نمودار، برخی از روش‌های طرح‌بندی سعی می‌کنند مستقیماً این معیارها را بهینه کنند.
* عدد متقاطع یک رسم تعداد جفت لبه‌هایی است که از یکدیگر عبور می‌کنند. اگر نمودار مسطح است، معمولاً ترسیم آن بدون هیچ گونه تقاطع لبه‌ها راحت است؛ یعنی در این مورد، ترسیم گراف نشان دهنده تعبیه گراف است. با این حال، نمودارهای غیرمسطح اغلب در برنامه‌های کاربردی به وجود می‌آیند، بنابراین الگوریتم‌های ترسیم گراف باید به‌طور کلی اجازه عبور از لبه را بدهند.
* مساحت یک نقشه به اندازه کوچک‌ترین جعبه مرزی آن است، نسبت به نزدیکترین فاصله بین هر دو راس. طرح‌هایی که مساحت کمتری دارند، عموماً بر آن‌هایی که مساحت بزرگ‌تری دارند ترجیح داده می‌شوند، زیرا به آنها اجازه می‌دهند ویژگی‌های نقاشی در اندازه بزرگ‌تر و بنابراین خواناتر نشان داده شوند. نسبت ابعاد جعبه مرزی نیز ممکن است مهم باشد.
* نمایش تقارن مشکل یافتن گروه‌های تقارن در یک نمودار معین و یافتن نقاشی است که تا حد امکان تقارن را نمایش دهد. برخی از روش‌های چیدمان به‌طور خودکار منجر به نقشه‌های متقارن می‌شوند. به‌طور متناوب، برخی از روش‌های ترسیم با یافتن تقارن‌ها در نمودار ورودی و استفاده از آن‌ها برای ساختن یک نقشه شروع می‌شوند.
* مهم است که لبه‌ها تا حد امکان ساده باشند تا چشم راحت تر آنها را دنبال کند. در نقشه‌های چند خطی، پیچیدگی یک یال را می‌توان با تعداد خم‌های آن اندازه‌گیری کرد، و هدف بسیاری از روش‌ها ارائه نقشه‌هایی با تعداد کمی خمش یا خم‌های کمی در هر لبه است. به‌طور مشابه برای منحنی‌های اسپلاین، پیچیدگی یک یال ممکن است با تعداد نقاط کنترل روی لبه اندازه‌گیری شود.
* چندین معیار کیفیت که معمولاً مورد استفاده قرار می‌گیرند، به طول لبه‌ها مربوط می‌شوند: به‌طور کلی مطلوب است که طول کل لبه‌ها و همچنین حداکثر طول هر لبه به حداقل برسد. علاوه بر این، ممکن است ترجیح داده شود که طول لبه‌ها یکنواخت باشد تا اینکه بسیار متنوع باشد.
* وضوح زاویه ای معیاری از واضح‌ترین زوایای یک نمودار است. اگر یک نمودار دارای رئوس با درجه بالایی باشد، لزوماً وضوح زاویه‌ای کوچکی خواهد داشت، اما وضوح زاویه‌ای را می‌توان با تابعی از درجه محدود کرد.
* تعداد شیب یک نمودار حداقل تعداد شیب لبه‌های متمایز مورد نیاز در نقاشی با لبه‌های پاره خط مستقیم است (اجازه دادن به عبور). نمودارهای مکعبی حداکثر دارای عدد شیب چهار هستند، اما نمودارهای درجه پنج ممکن است دارای عدد شیب نامحدود باشند. اگر تعداد شیب نمودارهای درجه ۴ محدود باشد، بازمی‌ماند.

## پانویس

## منابع

* .
* .
* .
* .
* .
* .

;زیرجستار تخصصی

* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .

## پیوند به بیرون
* GraphX library for .NET : کتابخانه منبع باز WPF برای محاسبه و تجسم نمودار. پشتیبانی از بسیاری از الگوریتم‌های طرح‌بندی و مسیریابی لبه.
* آرشیو چاپ الکترونیکی ترسیم نمودار: شامل اطلاعات روی مقالات از تمام سمپوزیوم‌های گراف طراحی.
*  برای بسیاری از پیوندهای اضافی مربوط به رسم گراف.
رده:رسم نمودار