graph homeomorphism

Let $G=(V,E)$ be a simple undirected graph.A simple subdivision is the replacement of an edge $(x,y)\\in E$ with a pair of edges $(x,z),(z,y)$ , $z$ being a new vertex, i.e., $z\ot\\in V$ .The reverse operation of a simple subdivisionis an edge-contraction through a vertex of degree 2.

Two graphs $G_{1}$ , $G_{2}$ are homeomorphicif $G_{1}$ can be transformed into $G_{2}$ via a finite sequence of simple subdivisionsand edge-contractions through vertices of degree 2.It is easy to see that graph homeomorphism is an equivalence relation.

Equivalently, $G_{1}$ and $G_{2}$ are homeomorphicif there exists a third graph $G_{3}$ such that both $G_{1}$ and $G_{2}$ can be obtained from $G_{3}$ via a finite sequence of edge-contractions through vertices of degree 2.

If a graph $G$ has a subgraph $H$ which is homeomorphic to a graph $G^{\\prime}$ having no vertices of degree 2,then $G^{\\prime}$ is a minor of $G$ .The vice versa is not true:as a counterexample, the Petersen graphhas $K_{5}$ as a minor, but no subgraph homeomorphic to $K_{5}$ .This happens because a graph homeomorphismcannot change the number of vertices of degree $d\eq 2$ :since all the vertices of $K_{5}$ have degree 4and all the vertices of the Petersen graph have degree 3,no subgraph of the Petersen graph can be homeomorphic to $K_{5}$ .

单词	GraphHomeomorphism
释义	graph homeomorphism Let $G=(V,E)$ be a simple undirected graph.A simple subdivision is the replacement of an edge $(x,y)\\in E$ with a pair of edges $(x,z),(z,y)$ , $z$ being a new vertex, i.e., $z\ot\\in V$ .The reverse operation of a simple subdivisionis an edge-contraction through a vertex of degree 2. Two graphs $G_{1}$ , $G_{2}$ are homeomorphicif $G_{1}$ can be transformed into $G_{2}$ via a finite sequence of simple subdivisionsand edge-contractions through vertices of degree 2.It is easy to see that graph homeomorphism is an equivalence relation. Equivalently, $G_{1}$ and $G_{2}$ are homeomorphicif there exists a third graph $G_{3}$ such that both $G_{1}$ and $G_{2}$ can be obtained from $G_{3}$ via a finite sequence of edge-contractions through vertices of degree 2. If a graph $G$ has a subgraph $H$ which is homeomorphic to a graph $G^{\\prime}$ having no vertices of degree 2,then $G^{\\prime}$ is a minor of $G$ .The vice versa is not true:as a counterexample, the Petersen graphhas $K_{5}$ as a minor, but no subgraph homeomorphic to $K_{5}$ .This happens because a graph homeomorphismcannot change the number of vertices of degree $d\eq 2$ :since all the vertices of $K_{5}$ have degree 4and all the vertices of the Petersen graph have degree 3,no subgraph of the Petersen graph can be homeomorphic to $K_{5}$ .
随便看	biquadratic extension BiquadraticField biquadratic field BirchAndSwinnertonDyerConjecture Birch and Swinnerton-Dyer conjecture BirkhoffKakutaniTheorem Birkhoff-Kakutani theorem BirkhoffPrimeIdealTheorem Birkhoff prime ideal theorem BirkhoffRecurrenceTheorem Birkhoff Recurrence Theorem BirkhoffvonNeumannTheorem Birkhoff-von Neumann theorem BirthdayProblem birthday problem BisectorsTheorem bisectors theorem BisimilarAutomata bisimilar automata Bisimulation bisimulation BitwiseAND bitwise AND BitwiseNOT bitwise NOT