Mathematical modeling and graph theory engleza

Theme 1

Introduction to graphs

1.1 Basic definitions

Definition 1.1.1. A graph (undirected graph, pseudo-graph, general

graph) is a pair G = (V,E), where:

- V is a finite nonempty set whose elements are called vertices (nodes,

points);

- E is a finite family (multiset) of unordered pairs of V whose elements

are called edges (lines).

Remark 1.1.1. For an unordered pair, denoted by [x, y], we have [x, y] = [y, x].

Definition 1.1.2. A digraph (oriented graph, pseudo-digraph) is a

pair G = (V,E) where:

- V is a finite nonempty set whose elements are called vertices (nodes,

points);

- E is a finite family (multiset) of (ordered) pairs of V whose elements

are called arcs (directed edges).

Remark 1.1.2. For a (ordered) pair, denoted by (x, y), we have (x, y) 6= (y, x)

if x 6= y.

Definition 1.1.3. The number of vertices of a graph or digraph G is called

the order of G, and the number of edges or arcs is called the size of G.

Definition 1.1.4. a) If e = [x, y] is an edge of a graph, then the vertices

x and y are called the endpoints of e, and we say that the edge e is

incident with x and y.

7

THEME 1. INTRODUCTION TO GRAPHS 8

b) If e = (x, y) is an arc of a digraph, then the vertices x and y are called

the tail and the head of e, respectively, and we say that the arc e is

incident with x and y.

c) A loop (self-loop) of a graph or digraph is an edge or an arc whose

endpoints coincide (i.e. an edge of the form [x, x], or an arc of the

form (x, x)).

d) An edge or an arc that is not a loop (i.e. its endpoints are distinct) is

called a proper edge, respectively a proper arc.

e) Two vertices x and y of a graph or digraph are called adjacent (neigh-

bors) if there exists an edge or an arc incident with x and y (i.e. an

edge of the form [x, y], respectively an arc of the form (x, y) or (y, x)).

Definition 1.1.5. a) Two or more edges, all of which have the same end-

points are called a multi-edge (multiple edges).

b) Two or more arcs, all of which have the same head and all of which

have the same tail are called a multi-arc (multiple arcs).

Definition 1.1.6. A graph or digraph without loops is called a multigraph

or multidigraph, respectively.

Definition 1.1.7. a) A simple graph is a graph with no loops or multi-

edges.

b) A simple digraph is a digraph with no loops or multi-arcs.

Remark 1.1.3. a) A simple graph is a pair G = (V,E), where V is a finite

nonempty set (whose elements are called vertices) and E ? P2(V ) is a finite

set (whose elements are called edges), where

P2(V ) = {{x, y}|x, y ? V, x 6= y}

(the set of all two-element subsets of V ).

b) A simple digraph is a pair G = (V,E), where V is a finite nonempty set

(whose elements are called vertices) and E ? V x V {(x, x)|x ? V } is a

finite set (whose elements are called arcs).

Definition 1.1.8. Let G = (V,E) be a graph or digraph. A graphical

representation of G can be obtained by drawing the vertices as points (in

the plane or in another surface) and the edges as lines (straight lines or

curves) connecting the end points. These lines are oriented if G is a digraph.

THEME 1. INTRODUCTION TO GRAPHS 9

Example 1.1.1. Consider the graph G = (V,E) with V = {1, 2, 3, 4, 5, 6}

and E = {e1, e2, e3, e4, e5, e6, e7, e8, e9}, where e1 = [1, 2], e2 = [1, 4], e3 =

[2, 2], e4 = [2, 5], e5 = [3, 6], e6 = [3, 6], e7 = [4, 5], e8 = [4, 5], e9 = [4, 5] (E is

a multiset!). This graph is represented in Figure 1.1.1. The graph G has the

[1] Gh. Barbu, V. Paun, Programarea in limbajul C/C++, Editura Matrix Rom,

Bucures, ti, 2011.

[2] C. Balcau, Combinatorica s,i teoria grafurilor, Editura Universitat, ii din Pites, ti,

Pites, ti, 2007.

[3] O. Basca, L. Livovschi, Algoritmi euristici, Editura Universitat,ii din Bucures, ti,

Bucures, ti, 2003.

[4] E. Ciurea, L. Ciupala, Algoritmi. Introducere in algoritmica fluxurilor in ret,ele, Ed-

itura Matrix Rom, Bucures, ti, 2006.

[5] T.H. Cormen, Algorithms Unlocked, MIT Press, Cambridge, 2013.

[6] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT

Press, Cambridge, 2009.

[7] C. Croitoru, Tehnici de baza in optimizarea combinatorie, Editura Universitat, ii "Al.

I. Cuza", Ias,i, 1992.

[8] N. Dale, C. Weems, Programming and problem solving with JAVA, Jones & Bartlett

Publishers, Sudbury, 2008.

[9] D. Du, X. Hu, Steiner Tree Problems in Computer Communication Networks, World

Scientific Publishing Co. Pte. Ltd., Hackensack, 2008.

[10] S. Even, Graph Algorithms, Cambridge University Press, Cambridge, 2012.

[11] S.C. Fang, J.R. Rajasekera, H.S.J. Tsao, Entropy Optimization and Mathematical

Programming, Kluwer Academic Publishers, Boston, 1997.

[12] H. Georgescu, Tehnici de programare, Editura Universitat, ii din Bucures, ti, Bucures, ti,

2005.

[13] S. Guias, u, Probabilistic Models in Operations Research, Nova Science Publishers,

New York, 2009.

[14] F.V. Jensen, T.D. Nielsen, Bayesian Networks and Decision Graphs, Springer, New

York, 2007.

[15] D. Jungnickel, Graphs, Networks and Algorithms, Springer, Heidelberg, 2013.

5

6

[16] B. Korte, J. Vygen, Combinatorial Optimization. Theory and Algorithms, Springer,

Heidelberg, 2012.

[17] L. Livovschi, H. Georgescu, Sinteza s, i analiza algoritmilor, Editura S, tiint, ifica s, i

Enciclopedica, Bucures, ti, 1986.

[18] C. Niculescu, Metode de optimizare patratica, Editura Universitat, ii din Bucures, ti,

Bucures, ti, 2006.

[19] D.A. Popescu, Bazele programarii - Java dupa C++, ebooks.infobits.ro, 2019.

[20] D.R. Popescu, Combinatorica s,i teoria grafurilor, Societatea de S, tiint, e Matematice

din Romania, Bucures, ti, 2005.

[21] N. Popescu, Data structures and algorithms using Java, Editura Politehnica Press,

Bucures, ti, 2008.

[22] V. Preda, C. Balcau, Entropy optimization with applications, Editura Academiei

Romane, Bucures,ti, 2010.

[23] T. Toadere, Grafe. Teorie, algoritmi s, i aplicat,ii, Editura Albastra, Cluj-Napoca,

2002.

[24] I. Tomescu, Combinatorica s, i teoria grafurilor, Tipografia Universitat,ii din

Bucures, ti, Bucures,ti, 1978.

[25] I. Tomescu, Probleme de combinatorica s, i teoria grafurilor, Editura Didactica s, i

Pedagogica, Bucures,ti, 1981.

[26] I. Tomescu, Data structures, Editura Universitat, ii din Bucures, ti, Bucures,ti, 2004.

[27] ***, Handbook of combinatorics, edited by R.L. Graham, M. Gr''otschel and L. Lov'asz,

Elsevier, Amsterdam, 1995.

[28] ***, Handbook of discrete and combinatorial mathematics, edited by K.H. Rosen,

J.G. Michaels, J.L. Gross, J.W. Grossman and D.R. Shier, CRC Press, Boca Raton,

2000.