Written Assignment # 6 Solution

$35.00 $29.00

Q.1 Which of these are posets? (R; =) (R; <) (R; ) (R; 6=) Q.2 Answer these questions for the partial order represented by this Hasse diagram. l m j k i h g d e f a b c Figure 1: Q.2 Find the maximal elements. Find the minimal elements. Is there a greatest…

5/5 – (2 votes)

You’ll get a: zip file solution

 

Description

5/5 – (2 votes)

Q.1 Which of these are posets?

  1. (R; =)

  1. (R; <)

  1. (R; )

  1. (R; 6=)

Q.2 Answer these questions for the partial order represented by this Hasse diagram.

l m

j

k

i

h

g

d

e

f

a

b

c

Figure 1: Q.2

  1. Find the maximal elements.

  1. Find the minimal elements.

  1. Is there a greatest element?

  1. Is there a least element?

  1. Find all upper bounds of fa; b; cg.

1

  1. Find the least upper bound of fa; b; cg, if it exists.

  1. Find all lower bounds of ff; g; hg.

  1. Find the greatest lower bound of ff; g; hg, if it exists.

Q.3 Let G be a simple graph with n vertices.

  1. What is the maximum number of edges G can have?

  1. If G is connected, what is the minimum number of edges G can have?

  1. Show that if the minimum degree of any vertex of G is greater than or equal to (n 1)=2, then G must be connected.

Q.4 Let n 5 be an integer. Consider the graph Gn whose vertices are the sets fa; bg, where a; b 2 f1; : : : ; ng and a 6= b, and whose adjacency rule is disjointness, that is, fa; bg is adjacent to fa0 ; b0 g whenever fa; bg\fa0 ; b0 g = ;.

  1. Draw G5.

  1. Find the degree of each vertex in Gn.

Q.5 Let G = (V; E)s be a graph on n vertices. Construct a new graph, G0 = (V 0 ; E0 ) as follows: the vertices of G0 are the edges of G (i.e., V 0 = E), and two distinct edges in G are adjacent in G0 if they share an endpoint.

  1. Draw G0 for G = K4.

  1. Find a formula for the number of edges of G0 in terms of the vertex degrees of G.

Q.6 Let G be a connected graph, with the vertex set V . The distance between two vertices u and v, denoted by dist(u; v), is de ned as the minimal length of a path from u to v. Show that dist(u; v) is a metric, i.e., the following properties hold for any u; v; w 2 V :

(i) dist(u; v) 0 and dist(u; v) = 0 if and only if u = v.

2

  1. dist(u; v) = dist(v; u).

  1. dist(u; v) dist(u; w) + dist(w; v).

Q.7 Show that if G is bipartite simple graph with v vertices and e edges, then e v2=4.

Q.8

  1. What is the sum of the entries in a row of the adjacency matrix for an undirected graph? For a directed graph?

  1. What is the sum of the entries in a column of the adjacency matrix for an undirected graph? For a directed graph?

Q.9 Show that isomorphism of simple graphs is an equivalence relation.

Q.10 Show that every connected graph with n vertices has at least n 1 edges.

Q.11 Explain how to nd a path with the least number of edges between two vertices in an undirected graph by considering it as a shortest path problem in a weighted graph.

Q.12 Which of the these nonplanar graphs have the property that the removal of any vertex and all edges incident with that vertex produces a palnar graph? a) K5 b) K6 c) K3;3 d) K3;4

3

Written Assignment # 6 Solution
$35.00 $29.00