isomorf [GRAF]

Martin Koutecký — 2021-11-16 11:09 (415 days ago) — reply

Které z následujících výroků o isomorfismu jsou správné? Svá trvzení zdůvodněte.
1. Grafy $G$ a $H$ jsou isomorfní, právě když pro každou bijekci $f: V(G) \rightarrow V(H)$ platí, že pro každé dva vrcholy $u,v \in V(G)$ platí následující ekvivalence:
 $$
  \{u,v\} \in E(G) \Leftrightarrow \{f(u),f(v)\} \in E(H).
 $$
2. Grafy $G$ a $H$ jsou isomorfní, právě když existuje bijekce $f: E(G) \rightarrow E(H)$.
3. Grafy $G$ a $H$ jsou isomorfní, právě když existuje bijekce $f: V(G) \rightarrow V(H)$ taková, že pro každý vrchol $v \in V(G)$ platí:
 $$
  \deg_G(v) = \deg_H(f(v))
 $$
4. Grafy $G$ a $H$ jsou isomorfní, právě když existuje zobrazení $f: V(G) \rightarrow V(H)$ takové, že pro každé dva vrcholy $u,v \in V(G)$ platí následující ekvivalence:
 $$
  \{u,v\} \in E(G) \Leftrightarrow \{f(u),f(v)\} \in E(H).
 $$
5. Každý graf s $n$ vrcholy je isomorfní nějakému grafu na množině vrcholů $\{1,\dots,n\}$.

Santa Claus — modified 2021-11-22 14:02 (409 days ago) — edit — reply

1\. Neplatí, z definice plyne, že stačí, aby existovalo jedno zobrazení. Můžu také uvést protipříklad: dva grafy $G = (\{A,B,C\}, \{\{A,B\}, \{B,C\}\})$ a $H = (\{1,2,3\}, \{\{1,2\}, \{2,3\}\})$ Tyto grafy jsou isomorfní protože existuje zobrazení, jedno z nich je $\{(1,A), (2,B),(3,C)\}$, ale například zobrazení  $\{(2,A), (1,B),(3,C)\}$ nesplňuje podmínku, protože mezi B a C je hrana, ale mezi 1 a 3 není.

2\. Z definice musí existovat zobrazení mezi vrcholy, ne jen mezi hranami. Protipříkladem by mohly být dva grafy, které nemají hrany a mají různý počet vrcholů. Neexistuje bijekce mezi vrcholy, tudíž nejsou isomorfní, přestože existuje prázdná bijekce mezi hranami.

3\. Neplatí, vezměme si kružnici na 6 vrcholech jako jeden graf a jako druhý graf graf složený z dvou trojúhelníků, kružnic na třech vrcholech. Každý vrchol má stupeň dva, ale grafy triviálně nejsou isomorfní.

4\. Neplatí, protipříklad: uvažme graf $G = (\{A,B,C\}, \{\{A,B\},\{B,C\}\})$ (cesta na třech vrcholech) a graf $H = (\{A,B\}, \{\{A,B\}\})$ a zobrazení $f = \{(A,A), (B,B),(C,A)\}$. Pro každou hranu platí daná ekvivalence, ale grafy nejsou isomorfní, protože nemají stejný počet vrcholů a tak mezi množinami vrcholů nemůže existovat bijekce.

5\. Platí, vezměme například úplně ten stejný graf s pouze přejmenovanými vrcholy, ten je k onomu grafu isomorfní a isomorfismem je ono přejmenovaní, které může být jakékoliv platné, případně i identita, pokud byl původní graf už na vrcholech $1...n$.

The Postal Owl

Diskrétní matematika

New post (You can use Markdown with KaTeX math here)