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 × 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. Păun, Programarea în limbajul C/C++, Editura Matrix Rom,
Bucures, ti, 2011.
[2] C. Bălcău, Combinatorică s,i teoria grafurilor, Editura Universităt, ii din Pites, ti,
Pites, ti, 2007.
[3] O. Bâscă, L. Livovschi, Algoritmi euristici, Editura Universităt,ii din Bucures, ti,
Bucures, ti, 2003.
[4] E. Ciurea, L. Ciupală, Algoritmi. Introducere în algoritmica fluxurilor în 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 bază în optimizarea combinatorie, Editura Universităt, 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 Universităt, 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, ifică s, i
Enciclopedică, Bucures, ti, 1986.
[18] C. Niculescu, Metode de optimizare pătratică, Editura Universităt, ii din Bucures, ti,
Bucures, ti, 2006.
[19] D.A. Popescu, Bazele programării - Java după C++, ebooks.infobits.ro, 2019.
[20] D.R. Popescu, Combinatorică s,i teoria grafurilor, Societatea de S, tiint, e Matematice
din România, Bucures, ti, 2005.
[21] N. Popescu, Data structures and algorithms using Java, Editura Politehnica Press,
Bucures, ti, 2008.
[22] V. Preda, C. Bălcău, Entropy optimization with applications, Editura Academiei
Române, Bucures,ti, 2010.
[23] T. Toadere, Grafe. Teorie, algoritmi s, i aplicat,ii, Editura Albastră, Cluj-Napoca,
2002.
[24] I. Tomescu, Combinatorică s, i teoria grafurilor, Tipografia Universităt,ii din
Bucures, ti, Bucures,ti, 1978.
[25] I. Tomescu, Probleme de combinatorică s, i teoria grafurilor, Editura Didactică s, i
Pedagogică, Bucures,ti, 1981.
[26] I. Tomescu, Data structures, Editura Universităt, 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.
