Math475 Graph Theory - 统计代写答疑辅导

分类： Math475 Graph Theory

数学代写|Math475 Graph Theory

Posted on 2023年3月27日2023年3月27日 by statistics-lab

Statistics-lab™可以为您提供umd.edu Math475 Graph Theory图论课程的代写代考和辅导服务！

Math475 Graph Theory课程简介

The content of this course includes general enumeration methods, which involves counting techniques used to solve combinatorial problems. The course also covers difference equations, which are used to model and solve recurrence relations. Another topic covered is generating functions, which are used to convert combinatorial problems into algebraic problems that can be solved using calculus and algebra.

In addition, the course includes elements of graph theory, which is the study of graphs and their properties. This includes matrix representations of graphs, which are used to analyze the structure of graphs. The course also covers applications of graph theory to transport networks, where graphs are used to model and analyze transportation systems.

Matching theory and graphical algorithms are also covered in this course. Matching theory is the study of matching problems, where we try to match elements from one set to another according to certain criteria. Graphical algorithms are algorithms that operate on graphs, and are used to solve problems such as shortest path and maximum flow problems.

PREREQUISITES

Sample Textbooks
First Course in Graph Theory, by Gary Chartrand
Introduction to Enumerative Combinatorics, by Miklos Bona
Applications
Computer science, physics, economics, biology, chemistry
If you like this course, you might also consider the following courses
MATH 401, MATH 405, MATH416, Study abroad program Budapest Semesters of Mathematics
Additional Notes
Students interested in grad school in STAT or computer science should consider this course. A large element of the course involves puzzles that are very easy to understand, but requiring thinking outside the box.

Math475 Graph Theory HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

3.1.7 Either draw the desired graph or explain why no such graph exists: A 9 vertex, 2-component, simple graph with exactly 10 edges and 2 cycles.

Let’s first consider the number of edges that a 2-component graph with 9 vertices can have. In order for a graph to have 2 components, it must be disconnected. The maximum number of edges in a disconnected graph with 9 vertices is achieved when one component has 8 vertices and the other has 1 vertex. In this case, the 8-vertex component can have at most 28 edges (a complete graph), and the 1-vertex component can have at most 0 edges. Therefore, the total number of edges in a 2-component graph with 9 vertices is at most 28.

Now, let’s consider the number of cycles that a 2-component graph with 10 edges can have. Each cycle in a simple graph must have at least 3 vertices, so the maximum number of cycles that a graph with 10 edges can have is achieved when each cycle has 3 edges. In this case, the total number of cycles is 10/3, which is not an integer, so there cannot be exactly 2 cycles in such a graph.

Therefore, there is no graph that satisfies all the given conditions.

问题 2.

3.2.2 Draw all rooted tree types with 5 vertices. How many different graph isomorphism types do they represent?

There are only two types of rooted trees with 5 vertices: the path tree and the star tree.

Path tree: This tree consists of a linear chain of 5 vertices, where each vertex has degree 1 except for the two endpoints, which have degree 1 and 2, respectively.

markdownCopy code     * --- * --- * --- * --- *
         1   2   3   4   5

Star tree: This tree consists of a central vertex with degree 4, and 4 leaves, each connected to the central vertex.

markdownCopy code           *
           |
     * --- * --- *
           |
           *

There are only two different graph isomorphism types for these trees, since any permutation of the vertices of the path tree or the star tree will result in an isomorphic tree of the same type. Therefore, there are 2 different graph isomorphism types for rooted trees with 5 vertices.

Textbooks

• An Introduction to Stochastic Modeling, Fourth Edition by Pinsky and Karlin (freely
available through the university library here)
• Essentials of Stochastic Processes, Third Edition by Durrett (freely available through
the university library here)
To reiterate, the textbooks are freely available through the university library. Note that
you must be connected to the university Wi-Fi or VPN to access the ebooks from the library
links. Furthermore, the library links take some time to populate, so do not be alarmed if
the webpage looks bare for a few seconds.

此图像的alt属性为空；文件名为%E7%B2%89%E7%AC%94%E5%AD%97%E6%B5%B7%E6%8A%A5-1024x575-10.png — Math475 Graph Theory

Statistics-lab™可以为您提供umd.edu Math475 Graph Theory图论课程的代写代考和辅导服务！请认准Statistics-lab™. Statistics-lab™为您的留学生涯保驾护航。

数学代写|Math475 Graph Theory

Posted on 2023年3月11日2023年3月11日 by statistics-lab

Statistics-lab™可以为您提供umd.edu Math475 Graph Theory图论课程的代写代考和辅导服务！

Math475 Graph Theory课程简介

PREREQUISITES

Math475 Graph Theory HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

2.6.7 Draw the graph with the adjacency matrix $A$. The vertices are in the order $a, b, c, d$
$$
A=\left(\begin{array}{llll}
0 & 1 & 1 & 1 \
1 & 0 & 1 & 0 \
1 & 1 & 0 & 1 \
1 & 0 & 1 & 0
\end{array}\right)
$$
2.6.15 Draw the digraph with the adjacency matrix $A$. The vertices are in the order $a, b, c, d$
$$
A=\left(\begin{array}{llll}
0 & 1 & 1 & 1 \
0 & 0 & 1 & 0 \
1 & 1 & 0 & 1 \
1 & 0 & 1 & 0
\end{array}\right)
$$
2.6.17 For the graph with the adjacency matrix $A$. (The vertices are in the order $a, b, c, d$ )
$$
A=\left(\begin{array}{llll}
2 & 1 & 1 & 1 \
1 & 0 & 1 & 0 \
1 & 1 & 0 & 1 \
1 & 0 & 1 & 0
\end{array}\right)
$$
Draw the graph $G$ and compute $A^2$ and show $A^2[a, a]$ is the number of paths of length two in $G$ from $a$ to itself. Show $A^2[d, a]$ does the same for paths of length two from $d$ to $a$.

2.6.7:

The graph with the given adjacency matrix is:

cssCopy codea -- b
| \/ |
| /\ |
c -- d

2.6.15:

The directed graph with the given adjacency matrix is:

markdownCopy codea -> b -> c <- d
^              |
|______________|

2.6.17:

The undirected graph with the given adjacency matrix is:

cssCopy code a -- b -- c
 |         |
 d---------

Computing $A^2$, we have:

A^2=\left(\begin{array}{cccc} 3 & 1 & 3 & 1 \\ 1 & 1 & 1 & 1 \\ 3 & 1 & 3 & 1 \\ 1 & 1 & 1 & 1 \end{array}\right)A2=⎝⎛3131111131311111⎠⎞

$A^2[a,a]$ counts the number of paths of length 2 from $a$ to itself in the graph $G$. There are 3 such paths: $a \to b \to a$, $a \to c \to a$, and $a \to d \to a$. Therefore, $A^2[a,a] = 3$.

$A^2[d,a]$ counts the number of paths of length 2 from $d$ to $a$ in the graph $G$. There is only 1 such path: $d \to b \to a$. Therefore, $A^2[d,a] = 1$.

问题 2.

1.6.1 Formulate the personnel-assignment problem [Application 1.3.1] as a maximum flow problem (Hint: add an artificial source and sink to the bipartite graph) (Hint page 262)
1.7.1 A 20-vertex graph has 62-edges. Every vertex has degree 3 or 7 . How many vertices have degree 3 ?
1.7.2 Either draw a 3-regular 7-vertix graph or prove that none exits.
1.7.3 Prove that no 5-vertex 7 -edge simple graph has diameter greater than 2.

1.6.1: The personnel-assignment problem can be formulated as a maximum flow problem as follows:

Consider the bipartite graph $G=(V,E)$ where $V= P \cup J \cup {s,t}$, where $P$ is the set of people, $J$ is the set of jobs, $s$ is an artificial source and $t$ is an artificial sink. For each person $i\in P$ and each job $j \in J$ such that $i$ is qualified for $j$, create an edge $(i,j)$ with capacity 1.

Connect $s$ to each person $i \in P$ with an edge $(s,i)$ and capacity $q_i$, the maximum number of jobs that person $i$ can be assigned to.

Connect each job $j \in J$ to $t$ with an edge $(j,t)$ and capacity 1.

The maximum flow from $s$ to $t$ in this graph corresponds to the maximum number of job assignments that can be made subject to the constraints that each person is assigned at most $q_i$ jobs and each job is assigned to at most one person. The assignment is found by taking the set of edges with non-zero flow, which corresponds to the set of job assignments.

1.7.1: Let $x$ be the number of vertices with degree 3 and $y$ be the number of vertices with degree 7. Then we have:

$$3x+7y = 2|E|=124$$

Since there are 20 vertices, we also have $x+y=20$. Solving these two equations gives $x=8$ and $y=12$. Therefore, there are 8 vertices with degree 3.

1.7.2: There are many 3-regular 7-vertex graphs, one example is the cycle graph $C_7$. Another example is the complete bipartite graph $K_{3,4}$.

To prove that no such graph exists, we can use the fact that the sum of the degrees of the vertices in any graph is twice the number of edges. In a 3-regular graph with 7 vertices, the sum of the degrees is $3 \times 7 = 21$, so the number of edges must be $21/2 = 10.5$, which is not an integer. Therefore, such a graph cannot exist.

1.7.3: Let $G$ be a simple graph with 5 vertices and 7 edges, and let $diam(G)$ be the diameter of $G$. Suppose for contradiction that $diam(G) > 2$. Then there exist two vertices $u$ and $v$ such that $d(u,v) > 2$.

Since $G$ has only 5 vertices, there must be at least one vertex $w$ that is adjacent to both $u$ and $v$. Without loss of generality, assume that $w$ is closer to $u$ than $v$ in terms of shortest path length. Then we have $d(u,w) \leq 1$ and $d(w,v) \leq 1$, so $d(u,v) \leq 2$, which contradicts the assumption that $d(u,v) > 2$. Therefore, we must have $diam(G) \leq 2$.

Textbooks

数学代写|Math475 Graph Theory

Posted on 2023年3月6日2023年3月6日 by statistics-lab

Statistics-lab™可以为您提供umd.edu Math475 Graph Theory图论课程的代写代考和辅导服务！

Math475 Graph Theory课程简介

PREREQUISITES

Math475 Graph Theory HELP（EXAM HELP， ONLINE TUTOR）

问题 1.

2.1.4 Find all possible isomorphisms tyepes of the given kind of simple graph: A 6-vertex tree.
2.1.8 Find all possible isomorphisms tyepes of the given kind of simple digraph: A simple 4-vertex digraph with exactly four arcs.

2.1.4 Solution:

A 6-vertex tree can have a maximum of 5 edges, as adding any more would create a cycle. Therefore, the possible isomorphism types of a 6-vertex tree are limited.

One possible 6-vertex tree is a straight line of 6 vertices, which we can label as 1, 2, 3, 4, 5, and 6. Another possible tree is a central vertex with 5 vertices branching out from it, which we can label as 1, 2, 3, 4, and 5. Other possible trees can be obtained by permuting the labels of these two trees.

Thus, there are only two possible isomorphism types for a 6-vertex tree: a straight line of 6 vertices, and a central vertex with 5 vertices branching out from it.

2.1.8 Solution:

A simple 4-vertex digraph with exactly four arcs can take on various shapes, as long as it has exactly four directed edges. We can label the vertices as 1, 2, 3, and 4.

One possible digraph is a cycle with vertices 1, 2, 3, and 4 in that order, where each vertex points to its immediate successor in the cycle. Another possible digraph is a straight line with vertices 1, 2, 3, and 4 in that order, where each vertex points to the next vertex in the line. Other possible digraphs can be obtained by permuting the labels of these two digraphs.

Thus, there are only two possible isomorphism types for a simple 4-vertex digraph with exactly four arcs: a cycle with vertices 1, 2, 3, and 4, or a straight line with vertices 1, 2, 3, and 4.

问题 2.

2.1.18 Find a vertex-bijection that specifies and isomorphism between the two digraphs:

oldq1.1 List all possible isomorphism types of trees with 6 edges carefully so that no two trees in your list are isomorphic.
oldq1.2 For the pair of graphs below, decide if they are isomorphic or not. If they are isomorphic, then give an isomorphism. If they are not isomorphic, then explain why they are not isomorphic.

2.1.18 Solution:

To find a vertex-bijection that specifies an isomorphism between the two digraphs, we need to find a mapping between their vertices that preserves adjacency. We can label the vertices of the first digraph as A, B, C, and D, and the vertices of the second digraph as 1, 2, 3, and 4.

One possible vertex-bijection that specifies an isomorphism between the two digraphs is:

A → 2 B → 1 C → 4 D → 3

This mapping preserves adjacency, since the vertices A and B are adjacent in the first digraph and their images 2 and 1 are adjacent in the second digraph. Similarly, the vertices C and D are adjacent in the first digraph and their images 4 and 3 are adjacent in the second digraph. Therefore, the two digraphs are isomorphic.

2.1.1 Solution:

For a tree with 6 edges, we know that it must have 7 vertices, as a tree with n vertices has n-1 edges. We can start by considering trees with a central vertex and 6 edges radiating out from it. If we label the central vertex as 1, then we can have the 6 edges connect to vertices labeled 2 through 7. However, this tree is isomorphic to a tree with the central vertex labeled as any of the vertices 2 through 7, since we can simply relabel the vertices to obtain the same tree.

Next, we can consider trees with two adjacent vertices of degree 3. If we label these vertices as 1 and 2, then we can have the remaining 4 edges connect to vertices labeled 3 through 7. However, this tree is isomorphic to a tree with the vertices labeled in any cyclic permutation of {1,2,3,4,5,6,7}, since we can simply rotate the tree to obtain the same tree.

Finally, we can consider trees with no vertices of degree 4 or higher. These trees must have at least 4 leaves, since a tree with fewer than 4 leaves must have a vertex of degree 4 or higher. We can start by considering trees with 4 leaves, which can be labeled as 1, 2, 3, and 4. We can then add a fifth vertex and connect it to any of the leaves, say vertex 1. We can then add a sixth vertex and connect it to any of the remaining leaves, say vertex 2. Finally, we add a seventh vertex and connect it to any of the remaining leaves, say vertex 3. There are three ways to choose the leaves to connect the fifth, sixth, and seventh vertices to, so there are three non-isomorphic trees with 6 edges and 7 vertices.

Therefore, there are a total of 4 non-isomorphic types of trees with 6 edges and 7 vertices.

2.1.2 Solution:

The two graphs are not isomorphic, since the first graph has a vertex of degree 4 (vertex B) and the second graph does not have any vertices of degree 4. In addition, the first graph has a cycle of length 3 (vertices A-B-C) and the second graph does not have any cycles of length 3. Since these properties are preserved under graph isomorphism, the two graphs cannot be isomorphic.