Matematické Fórum

nech G je nespojitý graf.
chcel by som určiť jeho polomer a vzialenosť medzi vrcholmi, medzi takými, kde existuje cesta.

polomer grafu je najmenšia možná excentricita vrcholov grafu. v definícii som nevidel nič, čo by hovorilo, že graf musí byť súvislý.

moje úvahy:

pre všetky vrcholy viem určiť excentricitu. tie vrcholy, kde nie je cesta, majú excentricitu nekonečno.
vyberiem si najmenšiu zo všetkých excentricitít a mám polomer grafu.
zaujímavé zistenie: polomer takéhoto grafu je nejaké konečné číslo n, zatiaľ čo jeho priemer je nekonečno.

s maticou susednosti však bude problém. keďže G je nesúvislý, tak žiadny riadok matice nebude obsahovať samé jednotky a teda nedokážem z nej určiť polomer. ale stále je možné z nej určiť že G je nesúvislý aj vzdialenosti medzi vrcholmi, kde existuje cesta.

otázka: má, či nemá nesúvislý graf polomer ? ak áno, dá sa nejako inak určiť z matice susednosti ?