Graflar uning turlari. Daraxtlar. Graflar va ularning turlari


Matrices and Directed Graphs



Download 0,76 Mb.
bet7/8
Sana18.12.2022
Hajmi0,76 Mb.
#890512
1   2   3   4   5   6   7   8
Bog'liq
37295 1Graflar maruza

Matrices and Directed Graphs
Consider the directedgraph shown inFigure 10.3.1. Thisgraph can be represented bythe matrix A= (aij) for which aij =the number of arrows from vi to vj, for all i =1,2,3 and j =1,2,3. Thus a11 =1 be cause there is one arrow from v1 to v1,a12 =0 be cause there is no arrow from v1 to v2,a23 =2 be cause there are two arrows from v2 to v3, an d so forth. A iscalled the adjacency matrix of the directed graph. For convenient reference, the rows andcolumns of A are often labeled with the vertices of the graph G.

Matrices and Undirected Graphs


Once you know how to associate a matrix with a directed graph, the definition of the matrixcorresponding to an undirected graph shouldseem natural to you.A s before, you must or der the vertices of the graph, but in thisc ase yous implyset the ijth entry of the adjacency matrix equal to the number of edgesconnecting the ith and jth vertices of the graph.
•Definition Let G be an undirected graph with ordered vertices v1,v2,...,vn. Theadjacency matrix of G is the n×n matrix A= (aij) over the set of nonnegative integers suc h that aij = the number of edgesconnecting vi and vj for all i, j =1,2,...,n.


Isomorphism Graphs

2.Thinking is a momentary dismissal of irrelevancies. — R. Buckminster Fuller, 1969


Recall from Example 10.1.3 that the two drawings shown in Figure 10.4.1 both repre- sent the same graph: Their vertex and edge sets are identical, and their edge-endpoint functions are the same. Call this graph G.

Observe that G$ is a different graph from G (for instance, in G the endpoints of e1 are v1 and v2, whereas in G$ the endpoints of e1 are v1 and v3). Yet G$ is certainly very similar to G. In fact, if the vertices and edges of G$ are relabeled by the functions shown in Figure 10.4.3, then G$ becomes the same as G.




Definition
Let G and G$ be graphs with vertex sets V(G) and V(G$) and edge sets E(G) and E(G$), respectively. G is isomorphic to G if, and only if, there exist one-to-one correspondences g: V(G) → V(G$) and h: E(G) → E(G$) that preserve the edge- endpoint functions of G and G$ in the sense that for all v ∈ V(G) and e ∈ E(G), v is an endpoint of e ⇔ g(v) is an endpoint of h(e).

Example 10.4.1 Showing That Two Graphs Are Isomorphic






Download 0,76 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish