Graph theory and simple circuit help

In summary, the conversation is about understanding and proving the existence of a simple circuit of length k in graph theory, and how it relates to isomorphism. The definition of a simple circuit is discussed, and the goal is to write a formal statement and prove it. The main point is that the existence of a simple circuit of length k is an isomorphism invariant.
  • #1
brad sue
281
0
Hi,
I have this problem I don't understand I have been on it for days now:

Show that the existence of a simple circuit of length k, where k is a positive integer greater than 2, is an isomorphism invariant.

please can someone help me with it?
Thank you
B.
 
Physics news on Phys.org
  • #2
Er, are you talking about graph theory?

What is the definition of

C is a simple circuit of length k?​

So what happens to C if you apply an isomorphism?
 
  • #3
Yes, it is graph theory.
A simple circuit is a path starting to a point and end to the same point, passing through each edge once.
So what happens to C if you apply an isomorphism?
I really don't have any idea!
 
  • #4
Okay, what is a path? We need to get to a formal statement, so that we can start proving things... so I'll cut to the chase. Using your definition of circuit (something feels slightly off, but I think it's minor, and I'll let you worry about it), a circuit of length k is:

(1) An alternating sequence of vertices and edges:
vertex_0, edge_1, vertex_1, edge_2, ..., edge_k, vertex_k

(2) The i-th edge is an edge between the (i-1)-th vertex and the i-th vertex.

(3) Every edge in your graph occurs exactly once in the sequence of edges.

(4) vertex_0 = vertex_k


So, can you write down a formal statement of what you're trying to prove?
 
  • #5
MMMM!
Not sure
What do you want me to understand is that 2 graphs are isomorphic if they both have a simple circuit of same length ( besides same # of vertices, edges and degree for vertices)??
Not sure Perhaps I an tired!
 
  • #6
What do you want me to understand is that 2 graphs are isomorphic if they both have a simple circuit of same length
Nope; that's backwards.

Show that the existence of a simple circuit of length k, where k is a positive integer greater than 2, is an isomorphism invariant.​

This wants you to show that if two graphs are isomorphic, then one has such a circuit iff the other does.
 
  • #7
Man! I still don't find it.
Please, I need more help with this problem.
 

1. What is graph theory?

Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures that represent relationships between objects. It is used to analyze and model complex systems such as computer networks, social networks, and transportation networks.

2. What is a simple circuit?

A simple circuit is a circuit that has a single closed loop, meaning that all of the components are connected in a continuous path. It can also be referred to as a series circuit. In a simple circuit, the current flows through each component in the same direction.

3. How is graph theory used in simple circuits?

Graph theory is used in simple circuits to analyze the flow of electricity and to determine the voltage, current, and resistance at different points in the circuit. It helps to identify the path of the current and to calculate the total resistance of the circuit.

4. What are the basic components of a simple circuit?

A simple circuit typically consists of a power source, such as a battery or a power supply, a load, such as a resistor or a light bulb, and connecting wires. These components are connected in a closed loop to allow the flow of electricity.

5. How do you calculate the total resistance in a simple circuit?

The total resistance in a simple circuit can be calculated by adding the individual resistances of all the components in the circuit. This can be done using Ohm's law (R = V/I) or by using the formula for calculating resistances in series (Rtotal = R1 + R2 + R3 + ...).

Similar threads

Replies
1
Views
777
  • Calculus and Beyond Homework Help
Replies
17
Views
881
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
4K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
492
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Introductory Physics Homework Help
Replies
1
Views
425
Back
Top