DOC PREVIEW
UNL CSCE 235 - Graphs

This preview shows page 1-2-3-4-26-27-28-53-54-55-56 out of 56 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IntroductionTypesClassesBipartite GraphsRepresentationsIsomorphismComputabilityExampleIdentifying `Candidates'ConnectivityEuler & HamiltonianGraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianGraphsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 9.1-9.5 of [email protected] / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction IGraph theory was introduced in the 18th century by LeonhardEuler via the K¨onigsberg bridge problem.In K¨onigsberg (old Prussia), a river ran through town thatcreated an island and then split off into two parts.Seven bridges were built so that pe ople could easily get around.Euler wondered, is it possible to walk around K¨onigsberg,crossing every bridge exactly once?2 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction II3 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction IIITo solve this problem, we need to model it mathematically.Specifically, we can define a graph whose vertices are the landareas and whose edges are the bridges.v1v2v3v4b0b1b2b3b4b5b64 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction IVThe question now become s, does there exist a path in thefollowing graph such that every edge is traversed exactly once?v1v2v3v4b4b5b6b0b1b2b35 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianDefinitions IDefinitionA simple graph G = (V, E) is a 2-tuple withV = {v1, v2, . . . , vn} – a finite set of vertices.E = V × V = {e1, e2, . . . , em} – an unordered set ofedges where each ei= (v, v0) is an unordered pair ofvertices, v, v0∈ V .Since V and E are sets, it makes sense to consider theircardinality. As is standard, |V | = n denotes the number ofvertices in G and |E| = m denotes the number of edges in G.6 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianDefinitions IIA multigraph is a graph in which the edge set E is amultiset. Multiple distinct (or parallel) edges can existbetween vertices.A pseudograph is a graph in which the edge set E canhave edges of the form (v, v) called loopsA directed graph is one in which E contains ordered pairs.The orientation of an edge (v, v0) is said to be “from v tov0”.A directed multigraph is a multigraph whose edges setconsists of ordered pairs.7 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianDefinitions IIIIf we look at a graph as a relation then, among other things,Undirected graphs are symmetric.Non-pseudographs are irreflexive.Multigraphs have nonnegative integer entries in theirmatrix; this corresponds to degree s of relatedness.Other types of graphs can include labeled graphs (each edgehas a uniquely identified label or weight), colored graphs (edgesare colored) etc.8 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyAdjacencyFor now, we will concern ourselves with simple, undirectedgraphs. We now look at some more terminology.DefinitionTwo vertices u, v in an undirected graph G = (V, E) are calledadjacent (or neighbors) if e = (u, v) ∈ E.We say that e is incident with or incident on the vertices u andv.Edge e is said to connect u and v.u and v are also called the endpoints of e.9 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyDegreeDefinitionThe degree of a vertex in an undirected graph G = (V, E) isthe number of edges incident with it.The degree of a vertex v ∈ V is denoteddeg(v)In a multigraph, a loop contributes to the degree twice .A vertex of degree 0 is called isolated.10 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyHandshake TheoremTheoremLet G = (V, E) be an undirected graph. Then2|E| =Xv∈Vdeg(v)The handshake lemma applies even in multi and pseudographs.proof By definition, each e = (v, v0) will contribute 1 to thedegree of each vertex, deg(v), deg(v0). If e = (v, v) is a loopthen it contributes 2 to deg(v). Therefore, the total degreeover all vertices will be twice the number of edges.11 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyHandshake LemmaCorollaryAn undirected graph has an even number of vertices of odddegree.12 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminology - Directed Graphs IIn a directed graph (digraph), G = (V, E), we have analogousdefinitions.Let e = (u, v) ∈ E.u is adjacent to or incident on v.v is adjacent from or incident from u.u is the initial vertex.v is the terminal vertex.For a loop, these are the same.13 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminology - Directed Graphs IIWe make a distinction between incoming and outgoing edgeswith respect to degree.Let v ∈ V .The in-degree of v is the number of edges incident on vdeg−(v)The out-degree of v is the number of edges incident fromv.deg+(v)14 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminology - Directed Graphs IIIEvery edge e = (u, v) contributes 1 to the out-degree of u and1 to the in-degree of v. Thus, the sum over all vertices is thesame.TheoremLet G = (V, E) be a directed graph. ThenXv∈Vdeg−(v) =Xv∈Vdeg+(v) = |E|15 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianMore Terminology IA path in a graph is a sequence of vertices,v1v2· · · vksuch that (vi, vi+1) ∈ E for all i = 1, . . . , k − 1.We can denote suc h a path by p : v1 vk.The length of p is the number of edges in the path,|p| = k − 116 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianMore Terminology IIA cycle in a graph is a path that begins and ends at the samevertex.v1v2· · · vkv1Cycles are also called circuits .We define paths and cycles for directed graphs analogously.A path or cycle is called sim ple if no verte x is traversed morethan once. From now on we will only consider simple paths andcycles.17 /


View Full Document

UNL CSCE 235 - Graphs

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Graphs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Graphs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graphs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?