موضوع مقاله: رسم گراف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # رسم گراف | مقدمه: ترسیم گراف حوزه‌ای از ریاضیات و علوم کامپیوتر است که روش‌های تئوری نمودار هندسی و تجسم اطلاعات را برای به دست آوردن تصاویر دو بعدی از گراف‌ها که از کاربردهایی مانند تجزیه و تحلیل شبکه‌های اجتماعی، کارتوگرافی، زبان‌شناسی و بیوانفورماتیک ناشی می‌شود، ترکیب می‌کند., pp. | ## بخش 1: رسم گراف | این طراحی نباید با خود گراف اشتباه گرفته شود: طرح‌بندی‌های بسیار متفاوت می‌توانند با یک گراف مطابقت داشته باشند., p. به‌طور انتزاعی، تنها چیزی که اهمیت دارد این است که کدام جفت رئوس توسط یال‌ها به هم متصل شده‌اند. با این حال، در بتن، چیدمان این رئوس و لبه‌ها در یک نقشه بر درک، قابلیت استفاده، هزینه ساخت و زیبایی‌شناسی آن تأثیر می‌گذارد., p. اگر گراف در طول زمان با افزودن و حذف یال‌ها تغییر کند (طراحی گراف پویا) مشکل بدتر می‌شود و هدف حفظ نقشه ذهنی کاربر است. قراردادهای گرافیکی گراف‌ها اغلب به عنوان گراف‌های پیوند گره ترسیم می‌شوند که در آن رئوس به صورت دیسک، جعبه یا برچسب‌های متنی و یال‌ها به صورت پاره خط، چند خط یا منحنی در صفحه اقلیدسی نمایش داده می‌شوند., p. گراف‌های پیوند گره را می‌توان به آثار شبه یوی قرن ۱۴ تا ۱۶ که با نام رامون یوی منتشر شده بود، بازمی‌گردد. شبه یوی نمودارهایی از این نوع را برای نمودارهای کامل به منظور تجزیه و تحلیل تمام ترکیبات زوجی در میان مجموعه‌ای از مفاهیم متافیزیکی ترسیم کرد.. در مورد نمودارهای جهت دار، نوک پیکان‌ها یک قرارداد گرافیکی رایج را تشکیل می‌دهند تا جهت خود را نشان دهند؛, p. با این حال، مطالعات کاربر نشان داده‌است که قراردادهای دیگر مانند مخروطی کردن این اطلاعات را به‌طور مؤثرتری ارائه می‌دهند.; . ترسیم مسطح رو به بالا از این قرارداد استفاده می‌کند که هر یال از یک راس پایین‌تر به یک راس بالاتر جهت‌گیری می‌شود و نوک پیکان را غیرضروری می‌کند.. | ## بخش 2: رسم گراف | قراردادهای جایگزین برای نمودارهای پیوند-گره شامل نمایش مجاورتی مانند بسته‌بندی دایره ای است که در آن رئوس با نواحی مجزا در صفحه و یال‌ها با مجاورت‌های بین نواحی نشان داده می‌شوند. نمایش‌های تقاطع که در آن رئوس با اجسام هندسی غیر متمایز و یال‌ها با تقاطع آنها نشان داده می‌شوند. نمایش‌های دید که در آن رئوس با نواحی در صفحه و لبه‌ها با مناطقی نشان داده می‌شوند که یک خط دید بدون مانع نسبت به یکدیگر دارند. نقشه‌های همرو، که در آن لبه‌ها به صورت منحنی‌های صاف در ریل‌های قطار ریاضی نمایش داده می‌شوند.. پارچه‌هایی که در آن گره‌ها به صورت خطوط افقی و لبه‌ها به‌عنوان خطوط عمودی نشان داده می‌شوند؛ و تجسم‌هایی از ماتریس مجاورت گراف. علاوه بر هدایت انتخاب بین روش‌های طرح‌بندی مختلف برای یک نمودار، برخی از روش‌های طرح‌بندی سعی می‌کنند مستقیماً این معیارها را بهینه کنند. اگر نمودار مسطح است، معمولاً ترسیم آن بدون هیچ گونه تقاطع لبه‌ها راحت است؛ یعنی در این مورد، ترسیم گراف نشان دهنده تعبیه گراف است. با این حال، نمودارهای غیرمسطح اغلب در برنامه‌های کاربردی به وجود می‌آیند، بنابراین الگوریتم‌های ترسیم گراف باید به‌طور کلی اجازه عبور از لبه را بدهند., p 14. مساحت یک نقشه به اندازه کوچک‌ترین جعبه مرزی آن است، نسبت به نزدیکترین فاصله بین هر دو راس. طرح‌هایی که مساحت کمتری دارند، عموماً بر آن‌هایی که مساحت بزرگ‌تری دارند ترجیح داده می‌شوند، زیرا به آنها اجازه می‌دهند ویژگی‌های نقاشی در اندازه بزرگ‌تر و بنابراین خواناتر نشان داده شوند. | ## بخش 3: رسم گراف | نمایش تقارن مشکل یافتن گروه‌های تقارن در یک نمودار معین و یافتن نقاشی است که تا حد امکان تقارن را نمایش دهد. به‌طور متناوب، برخی از روش‌های ترسیم با یافتن تقارن‌ها در نمودار ورودی و استفاده از آن‌ها برای ساختن یک نقشه شروع می‌شوند., p. در نقشه‌های چند خطی، پیچیدگی یک یال را می‌توان با تعداد خم‌های آن اندازه‌گیری کرد، و هدف بسیاری از روش‌ها ارائه نقشه‌هایی با تعداد کمی خمش یا خم‌های کمی در هر لبه است. به‌طور مشابه برای منحنی‌های اسپلاین، پیچیدگی یک یال ممکن است با تعداد نقاط کنترل روی لبه اندازه‌گیری شود. چندین معیار کیفیت که معمولاً مورد استفاده قرار می‌گیرند، به طول لبه‌ها مربوط می‌شوند: به‌طور کلی مطلوب است که طول کل لبه‌ها و همچنین حداکثر طول هر لبه به حداقل برسد. علاوه بر این، ممکن است ترجیح داده شود که طول لبه‌ها یکنواخت باشد تا اینکه بسیار متنوع باشد. اگر یک نمودار دارای رئوس با درجه بالایی باشد، لزوماً وضوح زاویه‌ای کوچکی خواهد داشت، اما وضوح زاویه‌ای را می‌توان با تابعی از درجه محدود کرد.. تعداد شیب یک نمودار حداقل تعداد شیب لبه‌های متمایز مورد نیاز در نقاشی با لبه‌های پاره خط مستقیم است (اجازه دادن به عبور). نمودارهای مکعبی حداکثر دارای عدد شیب چهار هستند، اما نمودارهای درجه پنج ممکن است دارای عدد شیب نامحدود باشند. | ## جمع‌بندی | آرشیو چاپ الکترونیکی ترسیم نمودار: شامل اطلاعات روی مقالات از تمام سمپوزیوم‌های گراف طراحی.