New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
mathematics
introduction to the mathematics

Introduction To The Mathematics Of Operations Research With Mathematica 1st Edition Kevin J Hastings - Solutions

Find the optimal vehicular flow for the traffic network with capacities below. Do this problem by hand, rather than in Mathematica. m Exercise 8
Let the intermediate nodes on the graph of Exercise 1 represent switching locations at a busy train station located at node 5 , to which trains are arriving from node 1.The edge capacities represent the number of parallel train tracks connecting switching locations. Use the maximal flow algorithm
The graph of Exercise 15 of Section 1.2 modeling a forced-air heat distribution system is displayed again below, with one additional edge. This time we suppose the fully connected system exists and due to pipe diameter differences, there are individual maximum airflow capacities on edges as shown
The diagram below represents the lubrication system of a machine; the lubricant flows from a source area at node 1 , through components \(2-6\), which require lubrication, and collects at node 7 . Edge capacities are maximum allowable flow rates from one position to another. Find the feasible flow
Devise a graph in which at some step the maximal flow algorithm will reduce the flow along a reverse edge.
Implement your own version of the AddFlow command described in this section.
In the problem of Example 3, suppose that in breadth-first search, vertex 4 is labeled first, before vertex 2 , so that vertex 3 will be labeled by vertex 4 rather than vertex 2 . Carry out the maximal flow algorithm by hand and note where a reverse edge arises in the algorithm.
Call a directed graph double quasi-connected if each pair of vertices has not only a common ancestor, but also a common descendant. Show that a double quasi-connected graph has both a root and a terminus.
Find all maximal trees and maximal paths for the graph of Figure 1.2.
Find all critical paths for the graph of Exercise 12 of Section 1.3 whose adjacency matrix is as below. Do this by hand, rather than with Mathematica. 4 3 4 2 936 5 2 215 622 4234 -
A job requires ten stages of work. The completion times for each are in the table below. Also listed in the table is the information of which stages cannot begin until other stages are complete, e.g., stage Drequires both stages A and B to be finished before it can begin. Find all critical
Finish the proof of Theorem 2 by showing assertion 2: If \((u, v)\) is an omitted edge and \(S(u, v)=0\), then the spanning tree created by substituting \((u, v)\) for the edge \(\left(u_{0}, v\right)\) currently in \(T^{*}\) is maximal.
A large computer program is to be tested and debugged in modules, some of which require other modules to be completely tested before testing on them can proceed. The table below shows the dependencies, and the times required to finish the testing and debugging of each module. How long does it take
Intuitively, it is clear what we mean when we say that a graph is a "line of vertices" (see below). Give a set-theoretic definition of a line of vertices, and show that if a directed network is not a line of vertices, then its underlying graph must have an undirected cycle.
An office wants to install an information system. The main tasks are below, with time estimates in days and task dependencies indicated. Find the amount of time required to get the system up and running, and find the set of tasks which could delay the project if they were delayed. Task A. Run
An advertising agency has contracted to prepare a commercial. The main tasks, time estimates, and task dependencies are shown in the table below. How many days will it take to produce this commercial? Task A. Write script 3 Time (days) Predecessor none B. Consult with client C. Revise script D.
For the project in Exercise 4, form a project graph with tasks on vertices.
A variation on the critical path problem is the task scheduling problem. In this problem, unlike the critical path problem, explicit attention is paid to how many workers are available to do tasks, and the goal is to assign and schedule tasks among workers so that predecessor conditions are
Use Kruskal's algorithm to find a minimal cost spanning tree for a graph whose vertices are labeled \(\{1,2, \ldots, 8\}\) and whose edges have the costs below: 146 51 25 321 1321 - - - - 2 - 21 - 8130 46 - 4 6358 54 +31 - 4 13214 - 32 26358 || 1011 |- | | | edge cost edge cost {1, 2} 2 {3, 7} 4 2
Cables are to connect several components of a sound system. The vertices in the graph below represent the components, and the edges are possible connections. The matrix above gives the lengths of cable required to connect each pair of components. Find the system of connections that requires the
In Example 2 compute the cost of the spanning trees formed by (a) breadth-first search; (b) ordering edges lexicographically. By how much do these costs differ from the total cost of the minimal spanning tree?
Suppose that the distances between fifteen cities are as in the table below, An airline wishes to institute service among these cities. Assuming that flight cost is directly proportional to distance, find an optimal routing system that provides service to all cities. City 1 2 3 4 5 6 7 8 9 10 11 12
Show that if a weighted, undirected graph \(G\) is connected and no two of its edges have the same cost, then there is a unique minimal spanning tree.
Explain why every vertex has component number 1 at the end of execution of Kruskal's algorithm.
Prove or disprove. Let \(T\) be a minimal spanning tree of an undirected graph \(G\) and fix a vertex \(v_{0}\). Then for each vertex \(u eq v_{0}\), the cost of the path in \(T\) from \(v_{0}\) to \(u\) is minimal among all paths in \(G\) from \(v_{0}\) to \(u\).
An amusement park wishes to run a tram line among several of its rides. The rides are nodes in the graph below, and the weights of the edges are distances between the nodes. Design a connecting system such that the least possible length of track will be used. 6 2 8 3 A I Exercise 8 7 3
An alternative algorithm for finding a minimal undirected spanning tree of a graph of \(n\) vertices is called Prim's algorithm. Begin with a single vertex. At any stage, check edges not in the spanning tree that have one vertex in the current incomplete tree (and one not in it). Add the edge of
Prove that Prim's algorithm of Exercise 9 yields a minimal spanning tree if the graph is connected. (Hint: Prove by induction that at each step the subgraph created by Prim's algorithm is connected and has no cycles, hence it is a tree, and moreover the Prim tree is contained in some minimal
Information is to flow from a source \(v_{0}\) to each of seven other locations labeled \(v_{1}, \ldots, v_{7}\) in the diagram below. Find a least costly way of doing this if the edge weights represent the costs of direct communication between nodes. Vo V3 Exercise 11
The matrix below gives the weights of directed edges connecting certain pairs of vertices in a directed graph. List shortest possible paths from vertex 1 to each other vertex in the network. 1215 121 136 21 4 3 4 31 + 52 4234
The vertices in the graph below are grain elevators, some of which can be connected by chutes to neighboring elevators, for the purpose of shifting grain from one location to another. The edges are directed because the chutes are inclined, to allow passage of grain by gravity in only one direction.
An alternative algorithm for finding the shortest path from the root \(v_{0}\) to each vertex \(v\) in a directed graph, called Dijkstra's algorithm, is as follows. Initialize the cost \(C(v)\) of a path to vertex \(v\) to be \(c\left(v_{0}, v\right)\) if there is such an edge, and \(+\infty\)
Prove that if a quasi-connected, directed graph with root \(v_{0}\) and positive costs is input to Dijkstra's algorithm (see Exercise 14), then for each \(v eq v_{0}\), a shortest path from \(v_{0}\) to \(v\) is returned. (Hint: Show inductively on the number of vertices added to \(S\) that the
Use Dijkstra's algorithm (see Exercise 14) to list shortest paths to all vertices \(v_{1}, \ldots, v_{7}\) in the graph of Exercise 11 Do this by hand, rather than with Mathematica.
A reservoir at vertex 1 in the diagram below is to supply water to several pumping stations. The edge weights are costs of laying pipe from one station to another. How should the pipe be laid so that all stations are served, but cost is minimized? Use (a) the policy improvement algorithm and (b)
Find a spanning tree of the graph below using the undirected spanning tree algorithm. Work by hand on this problem rather than using Mathematica. Assume that the order of the edges is:\(\{1,2\},\{2,5\},\{2,3\},\{4,7\},\{2,6\},\{1,4\},\{2,4\},\{3,4\},\{6,7\},\{5,6\},\{4,5\}\) 7
what spanning tree does the Spanning Tree One Step function find when the order of edges is:(a) \(\{\{5,6\},\{4,5\},\{3,4\},\{2,6\},\{2,5\}\),\(\{2,4\},\{2,3\},\{1,6\},\{1,5\},\{1,4\},\{1,3\},\{1,2\}\}\)(b) Determined by increasing order of cost. (See Figure 1.1)Compute the total edge cost for each
Suppose that \(G=(V, E)\) is a connected graph and \(\{u, v\} \in E\) is an edge in some cycle. Show that the graph \(G^{\prime}=(V, E)-\{u, v\}\) is connected. (This fact was used in the proof of Theorem 2.)
Prove that a connected, undirected graph \(G\) is a tree if and only if for each edge \(\{u, v\} \in G, G-\{u, v\}\) is not connected.
The graph below shows computer links between an official vote-tallying center at vertex 1 and several precincts. For the sake of secrecy, links can be made secure, but since this is an expensive process, it is desired to secure the minimum possible number of links and let the transmissions occur
Prove that if \(G\) is an undirected tree with more than one vertex, then \(G\) contains at least two vertices of degree 1 .
Finish the proof of Theorem 1, that is, if \(G\) is a connected graph with \(n\) vertices and \(n-1\) edges, then \(G\) is a tree.
Consider two connected components of an undirected graph \(G\), and suppose each has no cycles. Let \(G^{\prime}\) be a new graph whose vertex set is the union of the vertex sets of the two components and whose edge set is the union of the two edge sets, together with a single edge \(\{u, v\}\),
Is it possible to construct an undirected tree whose eight vertices have degrees \(1,2,3,3,1,1,3\), and 2 , respectively? Why, or why not?
Write your own version of the Convert To Adj Matrix [edgelist, n] command without options, which takes a list of edges of an undirected graph and the number of vertices in the graph, and returns the adjacency matrix.
Using the work already done in creating the Spanning Tree One Step function, write a full, simplified version of the complete undirected spanning tree algorithm, without the options, which takes the list of edges and the number of vertices in the graph, and returns the list of edges in a spanning
A complete undirected graph is a graph such that edges exist between every pair of vertices. Find an upper bound for the number of spanning trees a complete graph can have.
Find a directed spanning tree of the following graph if one exists. Is the tree unique? Do this by hand and not in Mathematica.
Vertices 8 and 18 are also roots in the graph of Figure 1.20. Check this using the Descendants function, and find directed spanning trees using each of these roots.
A forced-air heat distribution system in a building must get heat from the central furnace at vertex 1 in the figure to each of the rooms located at the other vertices. It is possible to mount ductwork, assumed unidirectional, along each of the edges shown on the graph. Find a sparsest possible
A directed graph has the adjacency matrix below. Use the Breadth First Tree function to find a directed spanning tree. Determine the root using the Descendants function.\[A=\left(\begin{array}{lllllllll} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0
Repeat Exercise 16 for the graph whose adjacency matrix is above. The root vertex is 7 .
Prove or disprove. A directed graph is a tree if and only if it is connected and has no directed cycles.
Prove or disprove. A directed graph is a tree if and only if it is quasi-connected and has no directed cycles.
Would the directed spanning tree algorithm also find an undirected spanning tree if the given graph was connected and undirected? Explain.
For the graph below, write the adjacency matrix \(A\), compute \(A^{3}\), and verify that for each \(i\) and \(j, A^{3}(i, j)\) is the number of paths from \(i\) to \(j\) of length 3 by listing those paths. 1 Exercise 1 3
Prove Theorem 1.
Show that the graph whose adjacency matrix is below has no cycles.\[ \left(\begin{array}{lllllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0
Show that there is no four-vertex undirected graph with degrees \(d\left(v_{1}\right)=3, d\left(v_{2}\right)=2, d\left(v_{3}\right)=2\), and \(d\left(v_{4}\right)=2\).
Write a Mathematica command that takes the adjacency matrix of a graph and a vertex, and returns the degree of that vertex. Test it on all the vertices of the graph of Figure 1.4.
Let \(A\) be the adjacency matrix of an undirected graph \(G\). Show that \(A^{2}(i, i)=d(i)\).
Two graphs \(G_{1}=\left(V_{1}, E_{1}\right)\) and \(G_{2}=\left(V_{2}, E_{2}\right)\) are called isomorphic if there is a one-to-one onto function \(f: V_{1} \rightarrow V_{2}\) such that for all \(v, w \in V_{1}\) edge \((v, w) \in E_{1}\) if and only if edge \((f(v), f(w)) \in E_{2}\). Show that
Argue, using the adjacency matrix only, that the graph in Figure 1.6 (a) is not connected.
There is a function in the KnoxOR`Graphs` package calledThis command returns a list of all children of vertices in the given list of parents, where adjmatrix is the adjacency matrix of a directed graph and a vertex \(v\) is a child of a vertex \(u\) iff there is an edge \((u, v)\) in the graph.
Prove that if the vertex set of a directed graph can be partitioned into three subsets \(V_{1}, V_{2}\), and \(V_{3}\) such that edges only exist from \(V_{1}\) into \(V_{2}\), or from \(V_{2}\) into \(V_{3}\), or from \(V_{3}\) into \(V_{1}\), then the graph is not regular. Give an example of such
Decide whether the following graph is (a) connected or (b) quasi-connected. ex12 = {{0, 1, 1, 0, 0}, {0, 0, 1, 1, 0}, {1, 0, 0, 0, 0}, (0, 0, 0, 0, 1}, {0, 1, 1, 1, 0}}; DisplayGraph[ex12, GraphType Directed, VertexLabelPositions (ToLeft, Above, Below, Above, ToRight}, EdgeSeparation .02,
Show that a connected directed graph is quasi-connected. Show that an undirected graph is quasi-connected if and only if it is connected.
For the graph of Figure 1.9, verify that \(A^{m}\) is not entirely non-zero for any \(m 3 2 Figure 1.9 - Paths of length 4 exist between each pair of vertices
Find all connected components of the graph below. 11 12 16
Argue that for undirected graphs, the connected components algorithm does find the connected component of the given initial vertex.
Prove that for directed graphs, the connected components algorithm finds the set of vertices that can be reached from a given initial vertex \(v\). Prove that this set is a closed set (see Example 7), and that if in addition every vertex \(u\) in the set can reach the initial vertex \(v\), then
For an undirected graph with the adjacency matrix below, find the connected components.\[ \left(\begin{array}{llllllllll} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 &
Write a Mathematica command that takes a weight matrix of a graph, and a list of vertices forming a path in the graph, and returns the weight of the path.
Adjacency matrices are not the only way of representing graphs. An adjacency list representation of a graph is a list, vertex-by-vertex, of the vertices that are adjacent to that vertex. For example, for the graph of Figure 1.4 one would have the adjacency list\[ \begin{aligned} & v_{1}:
Devise a way of implementing in Mathematica an adjacency list representation of a graph. (See Exercise 19.) Write a function that converts an adjacency list to an adjacency matrix.Data from in Exercise 19Adjacency matrices are not the only way of representing graphs. An adjacency list

Showing 500 - 600 of 575

1
2
3
4
5
6

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved