请输入您要查询的字词:

 

单词 GraphHomomorphism
释义

graph homomorphism


We shall define what a graph homomorphism is between two pseudographsMathworldPlanetmath, so that a graph homomorphism between two multigraphsMathworldPlanetmath, or two graphs are special cases.

Recall that a pseudograph G is an ordered triple (V,E,i), where V is a set called the vertex set of G, E is a set called the edge set of G, and i:E2V is a map (incidence map), such that for every eE, 1|i(e)|2.

Elements of V are called vertices, elements of E edges. The vertex/vertices associated with any edge e via the map i is/are called the endpointMathworldPlanetmath(s) of e. If an edge e has only one endpoint, it is called a loop. e1 and e2 are said to be parallelMathworldPlanetmathPlanetmath if i(e1)=i(e2).

As two examples, a multigraph is a pseudograph such that |i(e)|=2 for each edge eE (no loops allowed). A graph is a multigraph such that i is one-to-one (no parallel edges allowed).

Definition. Given two pseudographs G1=(V1,E1,i1) and G2=(V2,E2,i2), a graph homomorphism h from G1 to G2 consists of two functions f:V1V2 and g:E1E2, such that

i2g=f*i1.(1)

The function f*:2V12V2 is defined as f*(S)={f(s)sS}.

A graph isomorphismMathworldPlanetmath h=(f,g) is a graph homomorphism such that both f and g are bijectionsMathworldPlanetmath. It is agraph automorphism if G1=G2.

Remarks.

  • In case when G1 and G2 are graphs, a graph homomorphism may be defined in terms of a single function f:V1V2 satisfying the condition (*)

    {v1,v2} is an edge of G1{f(v1),f(v2)} is an edge of G2.

    To see this, suppose h=(f,g) is a graph homomorphism from G1 to G2. Then f*i1(e)=f*({v1,v2})={f(v1),f(v2)}=i2(g(e)). The last equation says that f(v1) and f(v2) are endpoints of g(e). Conversely, suppose f:V1V2 is a function sastisfying condition (*). For each eE1 with end points {v1,v2}, let eE2 be the edge whose endpoints are {f(v1),f(v2)}. There is only one such edge because G2 is a graph, having no parallel edges. Define g:E1E2 by g(e)=e. Then g is a well-defined function which also satisfies Equation (1). So h:=(f,g) is a graph homomorphism G1G2.

  • The definition of a graph homomorphism between pseudographs can be analogously applied to one between directed pseudographs. Since the incidence map i now maps each edge to an ordered pair of vertices, a graph homomorphism thus defined will respect the “direction” of each edge. For example,

    \\xymatrixa\\ar[r]&b\\ar[d]c\\ar[u]&d\\ar[l]        \\xymatrixr\\ar[r]&st\\ar[u]\\ar[r]&u\\ar[u]

    are two non-isomorphic digraphsMathworldPlanetmath whose underlying graphs are isomorphic. Note that one digraph is strongly connectedPlanetmathPlanetmath, while the other is only weakly connected.

Titlegraph homomorphism
Canonical nameGraphHomomorphism
Date of creation2013-03-22 16:04:53
Last modified on2013-03-22 16:04:53
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id11
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 05C75
Classificationmsc 05C60
Synonymgraph automorphism
Related topicGraphIsomorphism
Related topicPseudograph
Related topicMultigraph
Related topicGraph

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 22:36:21