Homeomorphism ???

Website: Moodle UK pro výuku 1
Kurs: Anglický jazyk pro matematiky II (2021)
Buch: Homeomorphism ???
Gedruckt von: Gast
Datum: Mittwoch, 17. Juli 2024, 12:39

1. Two terms

First, we need to note that there are two rather similar terms that can both be used in graph theory, and both denote a type of mapping, i.e. homeomorphism, and homomorphism.

Interestingly, if we analyse these terms only from the ethymological perspective, they mean the same:

homo and homeo are both derived from the Greek word for "same"
morphism is related to the word for "shape, form".

Both of these terms therefore refer to a mapping that in some sense preserves the form. 

1.1. Homomorphism

Given its general meaning, the mapping can be defined between many kinds of mathematical objects, graphs being just one of them. 

For the precise definition for graphs and its comparison with isomorphism see this perfect video:

It provides an extremely clear definition with examples.

Graph homomorphism is a useful concept in the area of graph colouring. 

1.2. Homeomorphism

Once again we will restrict ourselves to the definition for graphs. 

A subdivision of a graph G is a graph H which can be derived from G by applying the following operation any number of times: replace an edge e = ab by a path (a, x1, . . . , xk, b), where x1, . . . , xk are an arbitrary number of new vertices; that is, vertices which were not in a previous subdivision. For convenience, G is also considered to be a subdivision of itself. Two graphs H and H' are called homeomorphic if they are isomorphic to subdivisions of the same graph G. (Jungnickel, 2008, p. 23)

In other words, the graphs H' and H are homeomorphic if you can obtain the graph H' from H by either 1) subdividing an edge with one or more vertices, or 2) merging two edges which share a vertex of degree 2 by taking this vertex away (see Figure 1).

 h1

Figure 1. The two processes of subdividing and merging an edge.

For example, we see that all the graphs in Figure 2 are homeomorphic.

homeomorphic

Figure 2. Homeomorphic graphs.

2. References

Jungnickel, D. (2008). Graphs, Networks and Algorithms (Third Edition). Springer.

Schwartzman, S. (1994). The words of mathematics: An etymological dictionary of mathematical terms used in English. Mathematical Association of America.