Здравейте,

Задачата за изчертаване а граф е наистина много сериозна и интересна и определено е извън обсега на този клуб. Отклоняването от главната тема обаче не е голяма рядкост, така че заради занимателната тема може да си го простим...

Преди изобщо да започнем да мислим за решение, трябва да измислим условието . Сигурен съм че не е проблем да се наредят върховете в кръг например и да се нарисуват ребрата или да се измисли подобен универсален метод за показване, но дали няма да се получи чисто и просто една малка непрогледна джунглица...? Според мен шанса е доста голям да стане точно така.

За да избегнем "джнуглирането" на графа, ние тряба да търсим добро (на английски термина е neat, ама още не съм закусвал и не успях да измисля подходящ превод - ако някой се сети да свирка) графично представяне на графа. Тук идва логичния въпрос какво аджаба значи добро? Сигурен съм, че ако ми покажат два графа, няма да ми е трудно да определя кой от двата е по-добре нарисуван, или ако ми дадат описание на достатъчно малък граф след няколко опита ще съм го нарисувал що годе добре. Ама сметачите са си от край време тъпи машинки и от дума не разбират (сега бих казал мамка му, ама няма...). За тази цел трябва да се измислят някакви формални критерии за оценка на това доколко едно представяне е добро. Поначало целите са две:
1) този, който гледа рисунката да може да добие максимална представа за структурата на графа
2) да е красивичко чудото, което сме сътворили (ей ви и тук един чесато срещан английски термин, съжелявам ако от него добиете по-ясно представа отколкото от моите обяснения на български : aesthetically pleasing).

Това са т.н. меки или слаби критерии (soft). Вече споменахме за интелектуалните ограничения на сметачите и за налобителните силни или твърди (hard) критерии. Ето няколко примерни:
1) минимизиране брой пресичания на ребрата;
2) търсене на оптимално отношение ширина/дължина на картинката (за да съвпадне например с това на монитора, телевизора, екрана на прожектора...);
3) минимизиране на дължината на най-дългото ребро (или на средната стойност от първите няколко най-дълги ребра). Не е гот да гледаш една линия през целия граф, нали? А, тук трябва да се отбележи, че все пак не искаме (не че може...поне не толкова лесно) дължината на отсечките в картинката да отговаря на дължината на ребрата. Ако си поставим това условие работата става по-дебела от повечето други работи...
4) Площ. Тук искаме хем, площта на картинката да е най-малка, хем да няма два върха които са по-близо от предварително фиксирано разстояние (иначе мога да ви го наблъскам графа в кибритена кутийка. Без клечките, резбира се!).

Ей такива неща има в една книга: The Algorithm Design Manual.
В едно сайтче пишеше следното:
The best book available for this problem is Graph Drawing: Algorithms for the Visualization of Graphs by Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ionnis G. Tollis.
За съжаление не съм имал шанса да се запозная с тази книга по-отблизо от страничката и в on-line книжарниците (

Съдържаниет е скрито
Влезте за да го видите