Graflar uning turlari. Daraxtlar. Graflar va ularning turlari

Bog’langan graf	Connected graph	Связанный граф
Grafning ikki uchi bog’langan deyiladi, agar shu uchlarni birlashtiruvchi yo’l bo’lsa. Agar grafning har qanday uchini birlashtiruvchi marshrut mavjud bo’lsa, bunday graf bog’langan graf deyiladi
zanjir	chain	цепь	Barcha qirralari turli bo’lgan (yo’l) marshrut zanjir deb ataladi. Agar zanjir turli uchlardan o’tsa, u oddiy zanjir deb ataladi.
	cycle	цикл	Yopiq zanjir “sikl” deb ataladi, turli uchlardan o’tuvchi “sikl”, oddiy “sikl”dir.
daraxt	tree	дерево	Siklga ega bo’lmagan bog’langan graf daraxt deb ataladi, uning qirralari esa shoxlaridir.
O’rmon	forest	лес	Siklsiz bog’lanmagan graf o’rmon deb ataladi.
To’r	net	сеть	S=(G, C) juftlik to’r deb ataladi, Bu yerda G=(X,A) ixtiyoriy orientirlangan (yo’naltirilgan)dir.
Qoplovchi daraxt	Spanning tree	Покрывающее дерево	“mo’ljallanmagan”, “orientirlanmagan”, “yo’naltirilmagan” graf berilgan bo’lsin. D(Y,J) daraxt grafning qoplovchi daraxti deyiladi, agarda X=Y va J Ening qismi bo’lsa.

Theme: Graphs and trees.

Literature:

1. 
   Susanna S.Epp. Discrete mathematics with applications fourth edition. 2011,2004,1995Brooks/ColeCengageLearning
   
2. 
   Thinking is a momentary dismissal of irrelevancies. — R. Buckminster Fuller, 1969
   
3. 
   Victor Adamchik. Graph Theory. Fall of 2005
   

Graphs and trees have appeared previously in this book asconvenient visualizations. For instance, a possibility tree shows all possible outcomes of a multistep operation with a finite number of outcomes for each step, the directed graph of a relation on a set shows which elements of the set are related to which a Hasse diagram illustrates the relations among elements in a partially orderedset, and a PERTdiagramshows which ta sks mus t precede which in e xecuting a project. In thischapter we present some of the mathematics of graphs and trees, discussing concepts sucha s the degree of a vertex, connectedness,E uler and Hamiltonian circuits, representation of graphs bymatrices,i somorphisms of graphs, the relation between the number of vertices and the number of edges of a tree, properties of rooted treesspan- ning trees, andshortest paths in graphs. Applications include uses of graphs and trees in the study of artificial intelligence, chemistry, scheduling problems, an d transportation systems.

10.1 Graphs: Definitions and Basic Properties
The whole of mathematics consists in the organization of a series of aids to the imagination in the process of reasoning. — Alfred North Whitehead, 1861–1947
Imagine an organization that wants to set up teams of three to work on some projects. In order to maximize the number of people on each team who had previous expe- rienceworkingtogethersuccessfully,thedirectoraskedthememberstoprovidenamesof their past partners. This information isd isplayed below both in a table and in a diagram.

Definition: A graph G consists of two finite sets: a nonemptyset V(G) of vertices and a set E(G) of edges, where eache dge is associated with a set consisting of either one or two verticescalled its endpoints. The correspondence from edges to endpoints is called the edge-endpoint function. An edge with just one endpoint iscalled a loop, and two or more distincte dges with the same set of endpoints are said to be parallel. An edge issaid to connect its endpoints; two vertices that are connected by an edge are called adjacent; and a vertex that is an endpoint of a loop issaid to be adjacent to itself. An edge issaid to be incident on each of it s endpoints, an d two edges incident on the same en dpoint are called adjacent. A vertex on which no e dges are incident iscalled isolated.

Example 10.1.1 Terminology Consider the following graph:

1. 
   Write the vertexset and the edge set, and give a table showing the edge-endpoint function. b. Find all edges that are incident on v1, all vertices that are adjacent to v1, all e dges that are adjacent to e1, all loops, all parallel edges, all vertices that are adjacent to themselves, an
   

One important class of graphsconsists of those that do not have any loops or parallel edges.Such graphs are called simple. In asimple graph, no two edgesshare the same set of endpoints, so specifying two endpoints is su fficient to determine an edge.