dm2

Card Set Information

Author:
ahogeboom
ID:
65002
Filename:
dm2
Updated:
2011-02-08 14:58:12
Tags:
discrete
Folders:

Description:
Discrete Modeling II exam 1
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user ahogeboom on FreezingBlue Flashcards. What would you like to do?


  1. simple graph
    graph consisting of vertices and edges conecting these vertices.
  2. multiple edges
    edges connecting the same verticies
  3. multigraph
    graph having multiple edges connecting the same vertices
  4. pseudograph
    a graph the may include loos, and possibly even multiple edges connecting the same pair of vertices
  5. directed graph
    • (digraph)
    • a graph (V,E) that consist of a non-empty set of vertices (V) and a set of directed edges (E). Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v
  6. simple directed graph
    a directed graph that has no loops or multiple directed edges
  7. directed mulitgraph
    directed graphs that may have multiple directed edges from a vertex.
  8. mixed graph
    a graph with both directed and undirected edges
  9. adjacent
    two vertices u and v in an undirected graph G are called adjacent (neighbors) in G if u and v are endpoints of an edge of G
  10. incident
    if e is associated with {u,v}, the edge e is called incident with the vertices u and v
  11. degree of a vertex in an undirected graph
    the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex, the degree of the vertex v is denoted deg(v)
  12. isolated vertex
    a vertex of degree zero
  13. pendant vertex
    vertex of degree one
  14. adjacent to/from a vertex
    when (u,v) is an edge of a graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u
  15. initial/terminal vertex
    the vertext is called the inital vertex of (u,v) and v is called the termial vertex
  16. in-degree
    in a graph with directed edges, the in-degree of a vertex v, denoted deg-(v), is the number of edges with v as their teminal vertex.
  17. out-degree
    in a graph with directed edges, the out-degree of a vertex v, denoted deg+(v), is the number of edges with v as their inital vertex
  18. complete graph
    the complete graph on n vertices, denoted Kn, is the simple graph that contains exactly one edge between each pair of distinct vetices.
  19. cycle
    the cycle Cn, n>3, consists of n vertices v1,v2,...,vn and edges {v1,v2}, {v2,v3},..., {vn-1,vn}, and {vn,v}
  20. wheel
    we obtain the wheel Wn when we add an additional vertex to the cycle Cn, for n>3, and connect this new vertex to each of the n vertices in Cn by new edges
  21. bipartite graph
    a simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two in V2) when this condition holds, we call the pair (V1,V2) a bipartite of the vertex set V of G.
  22. complete bipartite graph
    • denoted Km,n
    • the graph that has its vertex set partitioned into 2 subsets of m and n vertices, repectively. There is an edge between two vetices if and only if one vertex is is the first subset and the other vertex is in the second vertex.
  23. subgraph of a graph
    a subgraph of a graph G=(V,E) is a graph H=(W,F), where WcV and FcE. A subgraph H of G is a proper subgraph of G if H / G
  24. union of 2 simple graphs
    graphs G1=(V1,E1) and G2=(V2,E2) is the simple graph with vertex set V1U V2 and edge set E1U E2. The union of G1 and G2 is denoted by G1U G2
  25. Handshaking Theorem
    • Let G=(V,E) be an undirected graphwith e edges. Then,
    • 2e = Σv=V deg(v)

    PROOF: each edge is incident with 2 vertices. when we add up the degrees, each edge will get counted twice. Thus, our sum will be twice the number of edges.
  26. Theorem 2
    an undirected graph has an even number of verices of odd degree.

    • PROOF: let V1 and V2 be the set of vertices of even degree and the set of vertices of odd degree, repectively, is an undirected graph G=(V,E). Then,
    • 2e = Σv=V deg(v) = Σv=V1 deg(v) + Σv=V2 deg(v)
    • we know Σv=V deg(v) is even so the Σv-v2 deg(v) must be even also to get 2e.
    • The only way add numbers sum to an even number is if there is an even number if them.
  27. Theorem 3
    • Let G=(V,E) be a graph with directed eged. Then,
    • Σv=V deg-(v) = Σv=V deg+(v) = |E|
    • sum of terminal degrees = sum of initial degrees = edges

    PROOF:
  28. Theorem 4
    a simple graph is bipartite is and only if it is possible to assign one of two different colors to each vertex of the graoh so that no two adjacent veritces are assignes the same color.

    PROOF:
  29. Havel/Hakimi
    a degree sequence with n>3 and d1>1 is graphical if and only if (d2-1, d3-1,..., dd1+1-1, dd+2,..., dn) is graphical.
  30. adjacency list
    • another way to represent a graph with no multiple edges
    • A----B
    • | .. \ .. |
    • C----D
    • vertex | adj. vertices
    • A | B, C, D
    • B | A, D
    • C | A, D
    • D | A, B, C
  31. adjaceny matrix
    • (or AG) of G with repsect to the listing of the vertices is an nxn matrix zero-one matrix with i as its (i,j)thentry with Vi is adjacent to Vj and 0 as its (i,j)th to entry when Vi and Vj are not adjacent.
    • aij = {1 if {Vi,Vj} is an edge of G
    • . . . . {0 other wise
  32. Incidence Matrix
    • Let G=(V,E) be an undirected graph. Suppose that v1,v1,...,vn are the vertices and e1,e2,...,en are the edges of G. The the incidence matrix with repsect to this ordering of V and E is the nxn matrix M=[mij] where
    • mij={1 when edge ej is incident with vi
    • . . . { 0 other wise
  33. Isomorphic Graph / Isomorphism
    the simple graph G1=(V1,E1) and G2=(V2,E2)are isomorphic if there is a one-to-one and onto function f from V1 to V2 with theproperty that a and b are adjacent in G1 if and only if f(a) and f(b) are adjjacent in G2, for all a and b in V1. Such a function f is called an isomorphism.

What would you like to do?

Home > Flashcards > Print Preview