проектирайте графика, където дървото на най-краткия път е по-дълго от минималното обхващащо дърво

Помислете за следната графика, където цената на ребра е написана между скоби:

1
|
|(1)
|
2
| \
|  \
|   \
|    \
|(25) \ (10)
|      \
3-------4     
   (20)

Тогава дървото с най-кратък път, вкоренено във връх 1, е:

1
|
|(1)
|
2
| \
|  \
|   \
|    \
|(25) \ (10)
|      \
3       4    

докато минималното обхващащо дърво на графиката е:

1
|
|(1)
|
2
  \
   \
    \
     \
      \ (10)
       \
3-------4     
   (20)

Що се отнася до втория ви въпрос, не можах да намеря отговор.

За да отговоря на втория ви въпрос: Ако графиката има n върха, дължината на дървото с най-кратък път е L, а дължината на минималното обхващащо дърво е K, тогава L ‹(n-1)K, но L може да бъде произволно близо до (n-1)K. За да видите защо L ‹ (n-1)K : всяко ребро в дървото с най-кратък път е по-малко от дължината на минималното обхващащо дърво. Има (n-1) от тях, следователно дължината на дървото с най-кратък път е по-малка от (n-1)K. Но разликата може да бъде произволно малка.

Разгледайте графиката, където връх 1 е на разстояние M, много голямо число, от връх 2,...,n. Разстоянията на всеки два върха сред 2,...,n са много малко число e. Тогава дължината на дървото с къс път с корен в 1 е (n-1)M, докато дължината на минималното обхващащо дърво е (n-2)e + M. Съотношението е приблизително (n-1), когато e е много малък и М е много голям.