Graph theory Definition and 156 Threads

I do not find option for that.

An incidence matrix reflects a relation on a set of ##n## objects ##1,2,\ldots,n## and is a square matrix with ##0##s on the diagonal, and ##0##s and ##1##s elsewhere. For example, consider the incidence matrix $$A=\begin{pmatrix}0&1&0&0\\ 1&0&0&1 \\ 0&1&0&1 \\ 1&1&0&0\end{pmatrix}.$$Since...

Hello! I wish to understand which lines and vertices in different 2D orthographic views of a 3D object correspond to each other. This information would also later be used to construct a 3D model from the 2D orthographic views. Blue shows matched edges/lines. Orange shows matched...

I have a unique problem and looking for a known fast algorithm for it. I have an unweighted but directed graph `G`. I then have a subset collection of nodes `S` existing in `G`. I want to find the minimum sub tree in `G` such that it contains all the nodes in `S`. I so far found Chu-Liu/Edmonds...

The eight regions

Hi, I've a question related to the graph theory. Take a connected graph with ##n## nodes and ##b## edges. We know there are ##m = b - n + 1## fundamental circuits. Which is the total number of nonempty circuits or edge-disjoint unions of circuits ? If we do not take in account the circuit...

I know that if an undirected graph is a tree then its number of edges satisfies ## |E| = |V| - 1 ##. If a directed graph ( digraph ) is a tree, is the result also true? ( I can imagine just taking an undirected tree and making its edges directed but this is specious since it's a little bit more...

Hi, I was reading through some slides about graph clustering. In the slides was a very short discussion about 'eigenvectors and segmentation'. I don't quite understand where one of the formulae comes from. Context: We have some undirected graph with an affinity matrix (i.e. weighted adjacency...

Hello everybody! I have to implement a sudoku solver in C ++ taking advantage by graph coloring theory, where each number to insert is a color of the associated graph node. In particular I would like to use the Welsh-Powell algorithm. I find myself in trouble starting with this project and I...

Attempt - I am stuck at this problem for hours, couldn't make any progress. Still, here's what I've done : Let ## e_1 \in E_1 \setminus E_2 ## be arbitrary. Suppose for the sake of contradiction that ## \forall ## ## e_2 \in E_2 \setminus E_1 ##, ## T_1' = \langle V,(E_1\setminus \{ e_1 \})...

Hello everybody, I hope it is the right section to post. For an exam, I should delve into a topic concerning graph theory. My work should include theoretical explanation, pseudo code, correctness analysis, complexity analysis and code implementation (C ++, python or other). Could someone...

We are working on an architectural project using graphs and we are looking for a way to combine separate graphs into one. We looked into methods to generate graph homorphisms, following the maximum graph homomorphism (MGH) (Langberg et al. 2006) and Paweł Rzążewski’s Exact Algorithm (2014)...

Given a minimal non-planar graph G, we need to find out if G', which is G-e, where e is a removed edge, we need to prove that there exists an edge e such that its removal would make G' a maximal planar graph. My idea in trying to figure this out would be by taking a minimal non-planar graph and...

Our problem involves a graph G that is simple and connected, where every biconnected component is a cycle that has at least four vertices in it. The maximum number of components we can get from removing a cut vertex is 4, and we are asked to find tight bounds on the chromatic number of G. My...

The problem is for us to consider a biconnected decomposition, and that proof for a graph, the degrees of all the vertices in a graph is even iff the degrees of all the vertices in all of its maximal biconnected components is even For solving that if the degrees of all the vertices in the...

In order to try and sovle this problem, my idea here was to use an extremal argument, with two equal length maximum paths on a tree. I said that no matter where the two graphs started, they'd end up having to cross paths since if there were two distinct paths with equal lengths the graph would...

For my base case I just used a graph with three vertices and 2 edges. Decomposing this would just give us the same graph, which has a path length of 2. The inductive step is where I'm having some trouble: One idea I have is that we take a graph G then inductively remove an edge to create two...

My Problem: Given a Graph G = (V,E), where the number of vertices is less than or equal to the number of edges, use induction to prove that the graph contains at least one cycle (the graph is not required to be completely connected). My attempt: For my base case, I used only one vertex with one...

Hello, recently I was looking into visiting Tokyo and started looking into its complicated but wonderfully efficient railway system. I picked 6 destinations in the area and looked up how much it would cost to go from anyone of the locations to any other. Then I started to wonder, if I...

Prove that if a simple graph G has 6 vertices then G or its complement has a subgraph isomorphic to ##K_3##. The proof begins by noting that is must be the case that G or its complement as a vertex with degree at least 3. Why is this the case?

Homework Statement Homework Equations Reduce the matrix to reduced matrix by removing 1 row completely Number of trees = determinant of [ Ar times ArT ] The Attempt at a Solution I removed 4th row to get Ar(reduced matrix) Then I did Ar times Ar (transpose) And found it's determinant but I...

Why should a person prefer irrational coordinate system over rational? My friend stated that its because most lines such as ##y=e## cannot be plotted on a rational grid system. But that cannot be true since ##e## does have a rational number summation ##2+1/10+7/100...## which can be utilised to...

Eugene Wigner once famously talked about the "unreasonable effectiveness of mathematics" in describing the natural world. Today again we are seeing this in action in particular with regard to the description of the biological brain from the perspective of neuroscience. Researchers from the Blue...

I'm playing around with Spectral Bisections and Fiedler vectors as ways of bisecting a graph using the sparsest cut. However, I'm finding that even the most trivially simple graphs are bisected incorrectly by this approach. What am I missing? Take for example a graph that is just a 4x4...

The complete graph K_n can be expressed as the union of k bipartite graphs iff n≤2^k I would simply like to know how to get 2^k.

I need recommendations on literature to read. Basically i do not understand these section of Frank Harary's book on graph theory since the definition of what a boundary and a cycle vector is not clearly defined. I have googled literature on it but I am having a tough time finding the right...

Hi! I'm struggling with these two problems: 1. If for whichever two vertices a and b in the graph G there is only one simple path from a to b, then the graph is a tree. Eh... isn't this part of the definition for a tree? I really don't even know where to start with proving this statements...

there's a proof provided, but i want to know the intuition as to why it is 2^k.

Homework Statement hello, I have this graph and i have to figure out these so to speak characteristics. 1) find incidence matrix 2) arrange peak according to rank and layers 3)draw new arranged graph 4) find new connection matricies of peaks and arcs Homework EquationsThe Attempt at a...

please check the attached photo

Homework Statement I am trying to verify this theorem for myself. Theorem: Every graph G containing a cycle satisfies g(G)≤2diam(G)+1 Homework Equations N/A The Attempt at a Solution i have drawn graphs and i failed to verify the theorem. is it even possible, since increasing the girth...

Proof: Let C be a shortest cycle in G. If g(G)>= 2diam(G) + 2, then C has two vertices whose distance in C is at least diam(G)+1. Question: why is it at least diam(G)+1? cont. of proof: In G, these vertices have a lesser distance; any shortest path P between them is therefore not a subgraph of...

Hi all, I am struggling the question, please see attachments. Thanks a lot Devise an algorithm which, given a (directed) friendship graph (in the xkcd format), finds the optimal seating arrangement. Your algorithm should include the following:  a description of the required input format...

Hello all, I recently starting studying graph theory in my free time and have become very interested in the Reconstruction Conjecture. Since I am new on the subject I am not sure where to start my search for additional information/insights/papers on the topic, I thought I would ask here for...

Homework Statement Given the representation of directed unweighted graph: typedef struct { int n;//num. of vertices void *info[MAX];//information of vertices int am[MAX][MAX];//adjacency matrix }GRAPH; Write a function int minDegree(GRAPH*); and int maxDegree(GRAPH*); that return the...

I just want something easy to boost my gpa and these are my two options. The geometry course is euclidean not topological. Thanks

I have read in many places that one necessary condition for the existence of a Euler circuit in a directed graph is as follows. Theorem: "A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree." However, I don't understand...

Homework Statement The problem is attached. I don't get this part. Let G = Sn be the group of all permutations of S. S is a set, so how can we permute something in a set?. Neither I know if the 4 power in the S is a typo. Homework EquationsThe Attempt at a Solution

Homework Statement The problem is attached and it's part A. There is no need to put problem 4 hence the problem is fully explained in the file attached Homework Equations Zk is mod k basically. The Attempt at a Solution I know that we have to prove that the transformation is onto,one to one...

Homework Statement Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3...

Hi, In the paper "A triangle-free circle graph with chromatic number 5" from A.A. Ageev, I don't understand what the author mean with the following definition: Somebody can explain it to me? (I'm not mathematician). Thanks ! Link to the whole paper...

Homework Statement 1. How many vertices will the following graphs have if they contain: (a) 12 edges and all vertices of degree 3. (b) 21 edges, three vertices of degree 4, and the other vertices of degree 3. (c) 24 edges and all vertices of the same degree. Homework Equations "Theorem 1 In...

Homework Statement I can't understand this paper. I understand the whole incidence matrix stuff, but I don't quiet get how it relates to the linear algebra. I don't know if this is allowed to do, but I will ask you questions line by line, so basically you will read the paper with me explaining...

Homework Statement A. Show that n^n−2/n! < T(n) by looking at how the symmetric group Sn acts on labelled trees. Use |Sn| = n! T(n) is the number of unlabeled trees on n vertices Homework EquationsThe Attempt at a Solution I can't find any mathematical relation between labelled trees and...

Homework Statement Exercise 0.1. Suppose that G is a finite graph all of whose vertices has degree two or greater. Prove that a cycle passes through each vertex. Conclude that G cannot be a tree. Homework EquationsThe Attempt at a Solution If every vertex in a graph G has degree two or...

Homework Statement Let G be a connected graph. We say that G is minimally connected if the removal of any edge of G (without deleting any vertices) results in a disconnected graph. (a) Show that a connected, minimally connected graph has no cycles. (b) Show that a connected graph with no cycles...

Homework Statement Prove that a complete graph with n vertices contains n(n − 1)/2 edges. Homework EquationsThe Attempt at a Solution The solution gives and inductive proof, but I am just wondering if this works as well. If we have a set of n vertices or points and we try to match all...

Homework Statement 1. Prove or disprove up to isomorphism, there is only one 2-regular graph on 5 vertices. Homework EquationsThe Attempt at a Solution I am making this thread again hence I think I will get more help in this section old thread...

Homework Statement 1. up to isomorphism, there is only one 2-regular graph on 5 vertices. Homework EquationsThe Attempt at a Solution I am still working on the problem, but I don't understand what up to isomorphism means. Does it mean without considering isomorphism?. I just need help with...

Homework Statement 1. Consider the Cartesian Product A X B, where A, B are finite nonempty sets, each with carnality greater than 1. There are two functions with domain A X B, called projections with mapping rules p1(a,b) = a and p2(a,b) = b. What is the target space of p1? p2? Are either of...