Επίπεδοι γράφοι...

Jeronymo Simonstone · #1

Θεωρήστε τους γράφους
$L_1,\ldots,L_n,\ldots$
που περιέχουν αντίστοιχα τους κόμβους
$\{l_1,\ldots,l_n\}\cup\{r_1,\ldots,r_n\}$
και ακμές
$\{E_{ij},i\geq j\}$
που συνδέουν τους κόμβους l_i

και

αντίστοιχα.

Ποιοι από τους γράφους είναι επίπεδοι και ποιοι όχι;
Για τους επίπεδους γράφους, να δωθεί κατάλληλη αναπαράσταση στο επίπεδο.

#2

Για $n \geqslant 5$ το υπογράφημα στις κορυφές $\{r_1,r_2,r_3,\ell_3,\ell_4,\ell_5\}$ είναι ένα $K_{3,3}$ που ως γνωστό δεν είναι επίπεδο. Άρα κανένα L_n

για $n \geqslant 5$ δεν είναι επίπεδο. Για $n \leqslant 4$ είναι όλα επίπεδα. Αφού το L_n

είναι υπογράφημα του L_4

για $n \geqslant 4$ αρκεί να δείξουμε ότι το L_4

είναι επίπεδο. Ο σχεδιασμός του είναι απλός αλλά παραλείπεται.

Jeronymo Simonstone · #3

πολύ σωστός

Και μερικά σχηματάκια.

Ο L_4

:

$\xymatrix{ l_1 \ar@{-}[r] & r_1 \\ l_2 \ar@{-}[ur] \ar@{-}[r] & r_2 \\ l_3 \ar@{-}[uur] \ar@{-}[ur] \ar@{-}[r] & r_3\\ l_4 \ar@{-}[uuur] \ar@{-}[uur] \ar@{-}[ur] \ar@{-}[r] &r_4 }$

ή, ισοδύναμα:

$\xymatrix{ & & & l_3 \ar@{-}[dll] \ar@{-}[d] \ar@{-}[dr]&\\ l_1 \ar@{-}[r]& r_1 \ar@{-}[r]& l_2 \ar@{-}[r]& r_2 & r_3 \\ & & & l_4 \ar@{-}[ull] \ar@{-}[d] \ar@{-}<span style="text-decoration:underline">\ar@{-}[ur] & \\ & & & r_4 \ar@{-}<span style="text-decoration:underline">&}$

#4

Πολύ ωραία τα σχήματα.

Επίπεδοι γράφοι...

Επίπεδοι γράφοι...

Re: Επίπεδοι γράφοι...

Re: Επίπεδοι γράφοι...

Re: Επίπεδοι γράφοι...

Μέλη σε σύνδεση