# Mathematical modeling and graph theory engleza

## Cuprins curs:

6 Steiner trees 56
6.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . 56
6.2 The Kou-Markowsky-Berman algorithm . . . . . . . . . . . . 58
7 Minimum weight spanning arborescences 70
7.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . 70
7.2 Counting spanning arborescences . . . . . . . . . . . . . . . . 71
7.3 Edmonds' algorithm . . . . . . . . . . . . . . . . . . . . . . . 72
8 Numerical invariants of graphs 81
8.1 Definitions and examples . . . . . . . . . . . . . . . . . . . . . 81
8.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
9 Maximum matchings 94
9.1 The Berge-Norman-Rabin theorem . . . . . . . . . . . . . . . 94
9.2 Edmonds' algorithm . . . . . . . . . . . . . . . . . . . . . . . 103
9.3 Perfect matchings . . . . . . . . . . . . . . . . . . . . . . . . . 123
10 Maximum flows in networks 127
10.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . 127
10.2 The algorithms of Ford-Fulkerson and Edmonds-Karp . . . . . 130
11 Invariants of a bipartite graph 150
11.1 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 150
11.2 K?onig's theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 152
11.3 Algorithmic consequences . . . . . . . . . . . . . . . . . . . . 158
12 NP-completeness 164
12.1 Algorithm complexity analysis . . . . . . . . . . . . . . . . . . 164
12.2 Nondeterministic algorithms. P and NP classes . . . . . . . . 168
12.3 NP-hard problems. NP-complete problems . . . . . . . . . . . 172
13 NP-hard problems in Graph Theory 177
13.1 Maximum clique problem . . . . . . . . . . . . . . . . . . . . . 177
13.2 Maximum stable set problem . . . . . . . . . . . . . . . . . . 184
13.3 Minimum (cardinality) transversal problem . . . . . . . . . . . 185
13.4 Minimum Steiner Tree problem . . . . . . . . . . . . . . . . . 186
14 Models of mathematical programming 191
14.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . 191
14.2 Constructing the geometric dual . . . . . . . . . . . . . . . . . 192
14.3 Duality theorems . . . . . . . . . . . . . . . . . . . . . . . . . 194
14.4 The linear programming case . . . . . . . . . . . . . . . . . . 199
14.5 Finding an "-optimal solution . . . . . . . . . . . . . . . . . . 200

## Extras din curs:

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

## Bibliografie:

[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.

Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.

Alte informații:
Tipuri fișiere:
pdf
Diacritice:
Nu
Nota:
9/10 (1 voturi)
Anul redactarii:
2020
Nr fișiere:
1 fisier
Pagini (total):
203 pagini
Imagini extrase:
203 imagini
Nr cuvinte:
45 127 cuvinte
Nr caractere:
221 854 caractere
Marime:
1.25 MB (arhivat)
Nivel studiu:
Facultate
Tip document:
Curs
Domeniu:
Limbaje de Programare
Data publicare:
16.02.2023
Structură de fișiere:
• Mathematical modeling and graph theory engleza.pdf
Predat:
la facultate
Te-ar putea interesa și:
UNIT 1 COMMUNICATION in BUSINESS Objectives: - become familiar with notions and importance of...
LECTURE NOTES 1 PERSPECTIVES ON INTERNATIONAL TOURISM 1. Introduction to global tourism The...
1. INTRODUCERE In conformitate cu dictionarul Oxford de ecologie modelul este o reprezentare a...
Sus!